(Array, Medium) Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

이 문제는 Find Minimum in Rotated Sorted Array 문제와 마찬가지로 O(log n) 시간복잡도를 요구한다.

또한 정렬된(rotated 되었지만) 배열을 대상으로 하므로 이분탐색 문제인 것을 알 수 있다.

다만 Find Minimum in Rotated Sorted Array 문제와 다른 점은 정확히 특정 인덱스에서 target을 찾을수 있는지 없는지 여부를 찾아야 한다는 것이다.

현재 mid값과 start/end 값 차이를 비교하여 부분 정렬된 배열인지 판단할 수 있다.

만약 nums[mid] >= nums[start]라면,
start부터 mid까지는 오름차순 정렬이 되어 있는 상태라고 볼 수 있다.
해당 배열은 rotated된 오름차순 배열이기 때문이다.
start~mid는 오름차순 정렬된 부분 배열이다.

그렇다면 start~mid가 오름차순 정렬된 상태에서 target을 찾기 위해 어떻게 범위를 축소해 나갈 수 있을까?

핵심은 target이 start와 mid사이에 있느냐? 이다.

if (nums[start] <= target && nums[mid] >= target)

정렬된 부분에서 target이 start~mid 사이에 있다면 end범위를 mid -1로 축소해주면 된다.

만약 start~mid가 오름차순 정렬이 되어 있으나 target이 start~mid 범위 안에 없다면 당연히 해당 범위를 벗어나 다른쪽 범위에서 탐색하기 위해 start를 mid +1 해주면 된다.

그러나 nums[mid] >= nums[start]가 아니라면 start~mid범위가 정렬된 상태가 아니기 때문에 범위 조절에 대한 별도의 로직이 필요하다.

그럼 여기서 또 비슷한 질문을 해야 한다.
핵심은 target이 mid부터 end 사이에 있느냐? 이다.

if (nums[end] >= target && nums[mid] <= target)

target이 mid~end 사이에 있다면 start가 mid + 1이 된다.
그 외라면(즉, mid부터 end사이에 target이 없다면) 해당 부분을 잘라낸다
end = mid -1

class Solution {
    public int search(int[] nums, int target) {

        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

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

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