[LeetCode] 33. Search in Rotated Sorted Array (C++)

문제

중복없이 오름차순으로 정렬된 정수 배열이 회전되어 있다.

target의 인덱스를 찾아라

O(log n)의 시간복잡도를 갖도록 하기

생각할 것

O(log n)의 시간복잡도를 갖기위해 이진 탐색을 이용하기

중간값과 양쪽 끝값 비교하기

코드

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        int mid;

        while(start <= end) {
            mid = (start + end) / 2;
            if(target == nums[mid]) return mid;
            if(nums[start] <= nums[mid]) { // 시작부터 중간까지 오름차순이 유지되어 있고,
                if(nums[start] <= target && target <= nums[mid]) { // target이 해당 범위에 들어가 있으면
                    end = mid - 1;
                }
                else {
                    start = mid + 1;
                }
            }
            else { // 시작부터 중간까지 오름차순이 아니면 
                if(nums[mid] <= target && target <= nums[end]) { // mid 이후의 범위 확인 
                    start = mid + 1;
                }
                else {
                    end = mid - 1;
                }
            }
        }

        return -1;
    }
};