JavaScript로 rotatedArray 이진탐색 구현하기

어떤 정렬된 array가 주어졌을 때, array는 오른쪽 혹은 왼쪽으로 rotate 될 수 있다.
ex) sorted array [0, 1, 2, 3, 4, 5, 6, 7] => rotated array [4, 5, 6, 7, 0, 1, 2, 3]

rotated array 내에서 target이 되는 숫자를 찾으려면 어떻게 해야 효율적으로 할 수 있을까?

주어진 array의 길이를 n이라고 하였을 때, O(n)이 아닌 O(log n)의 복잡도로 해당하는 숫자와 일치하는 자리의 index를 반환하는 문제를 풀어보았다.

수도코드

rotate이라는 표현으로 짐작가능한 것은, rotate을 시키는 기준점(pivot) 값이 존재한다는 것이다. 위에서 나타낸 sorted array가 rotated array로 바뀌는 경우는, 4,5,6,7의 묶음과 0,1,2,3의 묶음으로 경계를 나눌 수 있다. 원본 array가 순차적으로 정렬되어있었으므로
이처럼 각각의 묶음을 기준으로 파고들어 검색을 반복한다면 n개의 원소를 모두 순회하지 않고도 target값의 비교가 가능해질 것이다.
그럼 묶음의 경계를 찾는 건 어떻게 해야 할까?

이진탐색 알고리즘을 풀었을 때 처럼, array 범위를 start와 end로 한정한 뒤,그 값들을 조건에 따라 계속하여 변경시켜주면 될 것이다.(다만 일반적인 이진탐색 알고리즘과 다르게 이 문제에선 조건에 따라서 크게 '두 경우'로 나뉘어진다. 아래 필기화면에서처럼 첫 인덱스와 중간 인덱스의 값을 비교한다.)
그리고 범위를 좁혀나가면서 갑자기 start와 end가 같아지는 시점이 발생할텐데 그 때는 반복문을 탈출하도록 한다.

코드로 작성해보면

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  
  let start = 0;
  let end = rotated.length-1
  
  while(start<=end){

    let mid = parseInt((start+end)/2)
      
    if(rotated[mid] === target){
        return mid;
    }
    if(rotated[start]<rotated[mid]){ //mid 왼편이 정렬 되어 있음
      if (target < rotated[mid] && rotated[start]<=target) { //이 부분에서 rotated[start]<=target 부분을 확실히 명시해줘야 한다! 이 조건을 충족하지 않으면 아래 조건식으로 옮겨가서 탐색해야 하기 때문!
        end = mid - 1;
      } else { //target> rotated[mid] 이거나, rotated[start]>target 이면 오른편 탐색으로 넘어간다
        start = mid + 1;
      }
    }
    else{ //mid 오른편이 정렬이 되어 있음
      if (rotated[mid] < target && target<=rotated[end]) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
      }
  }
  return -1;
};