rotated Array Search with O(log n) - javascript

어떤 정렬된 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를 반환하여라.
해당하는 숫자가 array 내에 없을 경우는 null을 반환하여라.
For instance:
rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2) === 5
rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100) === null
O(n)이었다면, 간단하게 array를 한 번만 순회하면 될 문제이다.
하지만 그것보다 더 짧은 시간에 답을 찾도록 O(log n)을 구현해야 한다.
log n의 복잡도는 순회해야 하는 범위가 계속해서 반으로 줄어들면 가능할 것이다.

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

let rotatedArraySearch = (rotated, target) => {
    let minIndex = 0;
    let maxIndex = rotated.length - 1;
    //초기값은 array의 크기를 기준으로 정의한다.

    while(minIndex <= maxIndex) {
    //minIndex와 maxIndex가 같아지는 시점은 array 내부에 대한 모든 검사가 종료되는 시점이다.

        let midIndex = Math.floor((minIndex + maxIndex) / 2);
        //midIndex는 계속해서 변하는 min max Index 값 범위 내에서 target을 찾는 기준점이 된다.

        if(target === rotated[midIndex]) {
            return midIndex;
            //target값과 같은 값을 찾으면 더이상 while문을 돌 필요가 없어지므로 return
        }

        if(rotated[midIndex] <= rotated[maxIndex]) {
            if(target < rotated[midIndex) {
                midIndex = minIndex + 1;
                //현재 묶음 내에서 중간 위치의 값보다 target이 크므로,
                //중간 위치보다 앞선 index의 값들은 비교할 필요가 없어진다.
                //때문에 midIndex 이후의 값과 maxIndex 값의 범위로 좁히게 된다.
            } else {
                midIndex = maxIndex - 1;
                //현재 묶음 내에서 중간 위치기 값보다 target이 작으므로,
                //중간 위치보다 뒤의 index의 값들은 비교할 필요가 없어진다.
            }
        } else if(rotated[midIndex] >= rotated[minIdnex]) {
            if(target > rotate[midIndex]) {
                   midIndex = minIndex + 1;
            } else {
                midIndex = maxIndex - 1;
            }
        }
    }
    //while문 내에서 target과 일치하는 값을 array에서 찾지 못하면 그대로 while문은 종료될 것이다.
    //때문에 함수는 null 값을 return 시키고 종료된다.
    return null;
}