[BinarySearch][Medium] 33. Search in Rotated Sorted Array

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

 

회전된 정렬된 숫자배열이 주어질 때, target 값을 찾고 있다면 그 index를 반환하라.

 

Binary search의 종합 선물세트 문제. 

 

우선 회전된 rotated index를 찾는다. 

 

이후 target 값을 검색하되, 실제 access해야 할 index는 (index+rotateIndex) % arraySize 이다. 

 

코드 

int searchMinIdxBS(vector<int>& nums, int left, int right)
{
    if (left > right)    return -1;

    // 1, 2, 3, 4, 5
    // 
    // 5, 1, 2, 3, 4
    // 4, 5, 1, 2, 3
    // 
    // 3, 4, 5, 1, 2
    // 2, 3, 4, 5, 1

    int mid = left + (right - left) / 2;
    if (nums[left]<=nums[mid] && nums[mid]<=nums[right])
        return left;
    else if (nums[left] >= nums[mid] && nums[mid] <= nums[right])
    {
        if (mid > 0 && nums[mid - 1] >= nums[mid]) return mid;
        return searchMinIdxBS(nums, left, mid - 1);
    }
    else
    {
        if (right > 0 && nums[right - 1] >= nums[right])   return right;
        return searchMinIdxBS(nums, mid+1, right);
    }
}
int searchRotatedTargetIdxBS(vector<int>& nums, int left, int right, int startIdx, int target)
{
    if (left > right)    return -1;

    int mid = left + (right - left) / 2;

    // 실제 대상 mid index에 회전된 양을 적용한다.
    int idxMid = (mid + startIdx) % nums.size();

    if (nums[idxMid] == target)     return idxMid;
    else if (nums[idxMid] > target)
        return searchRotatedTargetIdxBS(nums, left, mid - 1, startIdx, target);
    else 
        return searchRotatedTargetIdxBS(nums, mid+1, right, startIdx, target);
}

// 33. Search in Rotated Sorted Array
int search(vector<int>& nums, int target)
{
    // find start min index first. 
    int startIdx = searchMinIdxBS(nums, 0, nums.size() - 1);
    if (startIdx < 0)    return -1;

    return searchRotatedTargetIdxBS(nums, 0, nums.size()-1, startIdx, target);
}

 

결과