solution 1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let hashMap = new Map();

    // all values of nums are unique
    for(let i = 0; i < nums.length; i++){
        hashMap.set(nums[i], i);
    }

    return hashMap.has(target) ? hashMap.get(target) : -1;
};

nums의 모든 값들이 unique하기 때문에 hash map을 만들고, target 값을 찾아 반환하면 된다.

접근법에 대한 고민

그러나, 문제 분류가 binary search로 되어있었고,
문제 조건에도 O(log N)의 시간 복잡도 내에 해결하기를 바랬기 때문에
이 방법은 적절한 풀이가 아니다.

그런데, binary search는 정렬된 데이터에 대해서만 사용할 수 있다.
nums는 정렬된 데이터를 임의의 k만큼 옆으로 이동시킨 배열이라, 정렬이 깨진 상태이다.
따라서, nums에 binary search를 사용하고자 한다면 추가적인 고민이 필요하다.

k를 알 수 없게 되어있으므로, middle을 구한다한들 정확한 지표로 활용할 수 없는 상태이다.
nums[middle]이 가장 작은 값이 될 수도, 큰 값이 될 수도, 이도저도 아닌 값이 될 수도 있기 때문이다.
따라서 binary search에서 흔히 사용하는 중간 인덱스인 middle로 기준을 잡으면 안된다.

일반적인 binary search를 위해 target과 middle을 사용하는 경우는 다음과 같다.

1. target < nums[middle]

2. nums[middle] < target

그러나 이 2개의 상황만이 전부는 아니다.
배열이 옆으로 이동한 상태이므로 target이 nums[middle]보다 작다고 해서 왼쪽에 있는게 아니기 때문이다.
그 대표적인 예시가 문제에 주어진 테스트 케이스인 [4,5,6,7,0,1,2]이다.

따라서 start, end도 같이 생각을 해줘야할 것으로 생각된다.

시도 1

각각의 경우에 대해서 더 세부적으로 나눠보자.

1. target < nums[middle]

• nums[start] < target : target은 start와 middle 사이에 있다.
• nums[start] > target : target은 middle과 end 사이에 있다.

그러나 여기서부터 문제가 생긴다.
[7,0,1,2,3,5,6]를 보면 알 수 있다. target이 0인 경우를 생각해보자.
middle은 1이 들어있는 2번 인덱스를 가리키고 있다.
이제 조건을 만족하는지 살펴보자.
1차 조건은 만족한다. 그러나 2차 조건에서 문제가 발생한다.
target은 nums[start]보다 작기 때문에 middle과 end 사이에 있어야하는데,
정반대로 start와 middle 사이에 존재하고 있기 때문이다.

조건을 수정해봐도 다른 케이스에 대해서 오답이 되기 때문에 역시나 진행이 되지 않는다.

따라서, 이 방법은 사용할 수 없다.

시도 2

시간 복잡도를 만족하기 위해서는 binary search를 사용해야만한다.
물론, 정렬을 하고 사용하면 좋겠지만, O(lon N)을 만족하는 정렬이 거의 없을 뿐더러
인덱스가 섞이기 때문에 정답을 얻기 위해서는 시간 복잡도를 다시 늘리는 현상이 발생할 것이다.
따라서, 최대한 정렬된 부분을 찾아서 탐색하는 것을 생각해보자.

앞서 말했듯이 nums는 원래 정렬된 배열이었으며,
솔루션 함수에 들어올 때 k만큼 옆으로 이동한 상태로 변경되어 들어온다.
따라서, 특정 인덱스를 선택해서 살펴보면 반드시 정렬이 된 상태로 존재하는 부분이 있을 것이다.

테스트 케이스의 원래 형태였을 [0,1,2,4,5,6,7]을 가지고 생각해보자.

아래의 경우가 발생할 수 있다. 정렬이 되어있던 상태는 제외하도록 한다.

[1,2,4,5,6,7,0]
[2,4,5,6,7,0,1]
[4,5,6,7,0,1,2]
[5,6,7,0,1,2,4]
[6,7,0,1,2,4,5]
[7,0,1,2,4,5,6]

이 때의 middle은 3번 인덱스이다.
middle을 기준으로 나눠보면 아래와 같다.

       ⬇️(middle)
[1,2,4,5,6,7,0] => [1,2,4] [5,6,7,0] 
[2,4,5,6,7,0,1] => [2,4,5] [6,7,0,1]
[4,5,6,7,0,1,2] => [4,5,6] [7,0,1,2]
[5,6,7,0,1,2,4] => [5,6,7] [0,1,2,4]
[6,7,0,1,2,4,5] => [6,7,0] [1,2,4,5]
[7,0,1,2,4,5,6] => [7,0,1] [2,4,5,6]

middle을 어느 쪽에 포함시켜도 로직은 같으니 일단 살펴보자.
분리된 것들 중 어느 한 쪽은 반드시 정렬된 형태를 가지고 있다.
정렬된 배열이 옆으로만 이동해서 입력되었기 때문에 당연한 말이긴 하다..
이 중에서 target이 들어있는 곳을 검색한다.

이 부분이 가장 중요할 것 같다. 접근을 잘못하면 시도 1 때와 같은 일이 발생하기 때문이다.
여기서도 마찬가지로 binary search의 핵심인 start, middle, end를 적절하게 활용해야겠다.

1. nums[start] <= nums[middle] : 왼쪽 배열이 정렬된 상태

• nums[start] <= target && target < nums[middle] : 왼쪽 배열에 target 존재
• 오른쪽 배열을 볼 필요가 없어졌다.
• end = middle - 1
• 만약, 위 조건을 만족하지 않는다면 오른쪽 배열에 target이 존재하므로, start = middle + 1

2. 그 외: 오른쪽 배열이 정렬된 상태

• nums[middle] <= target && target <= nums[end] : 오른쪽 배열에 target 존재
• 왼쪽 배열을 볼 필요가 없어졌다.
• start = middle + 1
• 만약, 위 조건을 만족하지 않는다면 왼쪽 배열에 target이 존재하므로, end = middle - 1

solution 2

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let start = 0;
    let end = nums.length - 1;
    
    while(start <= end){
        let middle = Math.floor((start + end) / 2);

        if(nums[middle] === target){
            return middle;
        }

        if(nums[start] <= nums[middle]){
            if(nums[start] <= target && target < nums[middle]){
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        } else {
            if(nums[middle] <= target && target <= nums[end]){
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
    }


    return -1;
};

시도 2를 적용한 풀이이다.
전체적으로 일반적인 binary search와 동일한 형태를 가지고 있다.
다만 start, end를 조절하는 부분에 조건이 추가되었을 뿐이다.