Leetcode - 33. Search in Rotated Sorted Array

문제

값이 정렬되어있는 배열이 있다. 그런데 특정 pivot 인덱스를 기준으로 회전되어있다. 이런 배열에서 target값의 index를 찾아라. 단 시간복잡도는 O(logN)을 초과할 수 없다.

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

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

해결

이런 정렬상태에서 binary search를 어떻게 해야하는지, 이런저런 조건을 만들어가며 궁리해봤는데 답이 안나와서 첨에 솔직히 막막했다. 그런데 어쨋든 결국 pivot을 찾기 위한 binary search 한번, 그리고 정상적인 정렬상태에서의 binary search한번 하는 방법으로 스스로 해결책을 찾았다. 뿌듯하다.

int bsearch_pivot(int *nums, int left, int right, int target)
{
    int mid = 0;
    while (left < right) {
        mid = (left + right) >> 1;
        if (mid + 1 <= right && nums[mid] > nums[mid + 1])
            return mid;
        else if (nums[mid] > nums[right])
            left = mid;
        else if (nums[left] > nums[mid])
            right = mid;
    }
    return left;
}

int bsearch_orig(int *nums, int left, int right, int target)
{
    int mid = 0;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (target == nums[mid])
            return mid;
        else if (target < nums[mid])
            right = mid - 1;
        else if (nums[mid] < target)
            left = mid + 1;
    }
    return -1; 
}
int search(int* nums, int numsSize, int target){
    int left = 0, right = numsSize - 1, pivot = 0;
    if (nums[left] > nums[right]) {
        pivot = bsearch_pivot(nums, left, right, target);
        if (nums[left] <= target && target <= nums[pivot])
            right = pivot;
        else
            left = pivot + 1;
    }
    return bsearch_orig(nums, left, right, target);
}