[Javascript] rotatedArraySearch

문제

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

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

입출력 예시

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(rotated, target){
	for(let i = 0; i < rotated.length; i++){ // rotated안에 전부 탐색
      if(rotated[i] === target){// 만약에 루프돌다 타겟값이 같다면
        return i; // i를 리턴하고 루프 종료
      }
    }  
  return -1; //그 안에 없다면 -1 리턴
}

하지만 추가적인 조건이 있는데

단순히 처음부터 끝까지 찾아보는 방법(O(N)) 대신 다른 방법(O(logN))을 탐구해 보세요.

O(logN)으로 만들려면 이진탐색을 쓰라는 것 같다. 그래서 참고를 해서 다시 만들어 보았다.

const rotatedArraySearch(rotated, target){
  let left = 0, right = rotated.length - 1; 
  
  while(left <= right){
    let middle = parseInt((left + right) / 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;
      }
    }
  }
}

제일 먼저 rotated배열의 맨 왼쪽과 오른쪽을 선언해주었다. 그래서 가운데 값을 구해서 먼저 그 값이 타겟과 같은지 비교한다. 같으면 middle을 리턴해 준다. 하지만 같지 않다면 맨 왼쪽값과 가운데 rotated[middle]값을 비교한다 이렇게 하는 이유는 미들값을 기준으로 절반을 잘라서 나머지를 검색해야하기 때문이다. 이렇게 왼쪽값이 오른쪽값보다 커질때까지 진행한다.
여기에서 이진탐색을 응용하는데 있어서 어려움이 있었다. 이렇게 한번보고 번뜩번뜩 생각이 나면 얼마나 좋을까....