(rotatedArraySearch) 부분적으로 정렬된 배열 정렬하기 Javascript

문제

부분적으로 오름차순 정렬된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

• 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
• 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.

주의 사항

• rotated에 중복된 요소는 없습니다.
• target이 없는 경우, -1을 리턴해야 합니다.

입출력 예시

let output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2);
console.log(output); // --> 5

output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100);
console.log(output); // --> -1

풀이

const rotatedArraySearch = function (rotated, target) {
	let left = 0;
    let right = rotated.length - 1;
    
    while(left <= right){
    	let middle = parseInt((right + left) / 2);
        if(rotated[middle] === target) {
        	return middle;
        }
        
        if(rotated[left] < rotated[middle]){
        	// 왼쪽으로 미는 경우
        	if(target < rotated[middle] && rotated[left] <= target){
            	right = middle - 1;
            } else {
            	left = middle + 1;
            }
        } else {
        	// 오른쪽으로 미는 경우
        	if(target <=  rotated[right] && rotated[middle] < target){
            	left = middle + 1;
            } else {
            	right = middle - 1;
            }
        }
    }
    return -1;
};

기존에 풀었던 binarySearch에 도움을 많이 받았고, 풀이 방법에 대해서 생각할 때 시간이 오래걸렸다. 스스로 풀었다는 느낌보다 검색을 통해 해결한 문제라 다시 한 번 봐야겠다.