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

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

Search in Rotated Sorted Array - LeetCode

 

Q. 주어진 오름차순 정렬된 배열 nums가 있다. 

 이 배열이 rotated 되어 있을 수 있을때, target이 있다면 그 index를 찾아라. 

 없으면 -1을 반환하라. 

 

 

Solution. 

 '꼬아놓은' binary search 문제다. 

 완료조건, 진행조건, 예외처리 

 이 세가지 중, 진행 조건에 조금 유의가 필요한 케이스 이다. 

 

 완료 조건은 명백하다. 

 mid value가 target이면 해당 mid의 index를 반환하면 된다. 

 

 진행 조건은 

   rotated 가 없을때 mid보다 target이 작으면 왼쪽, 크면 오른쪽으로 진행 하면 된다. 

   rotated가 mid의 왼쪽에 있을때,  mid의 오른쪽범위는 여전히 정렬되어 있으므로, target이 오른쪽 범위이면 오른쪽진행, 아니면 왼쪽 진행 한다. 

   rotated가 mid의 오른쪽에 있을때는 그 반대로 한다. 

 

  그렇다면 rotated는 어떻게 찾는가. 

 

   nums가 1, 2, 3, 4, 5 라고 할때 

   1, 2, 3, 4, 5 에서 left는 1, mid는 3, right 는 5이다. 

   각각이 순차적인 크기이면 rotated가 없다고 볼수 있다. 

 

   5, 1, 2, 3, 4 

   4, 5, 1, 2, 3 

   mid가 left, right 값에 비해 최소 값이다. 

   이때는 rotated가 정확한 위치는 모르나 일단 왼편에 있다고 판단할 수 있다.  

    

   3, 4, 5, 1, 2 

   2, 3, 4, 5, 1 

   mid가 left, right 값에 비해 최대값이다. 

   이때는 rotated가 mid의 오른편에 있다고 판단할 수 있다. 

 

   배열의 구성에 관계없이 rotated의 경우는 이정도가 다 일 것이다.

 

   로직대로 코드를 만들어 본다. 

 

  

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

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

    int leftV = nums[left];
    int rightV = nums[right];
    int midV = nums[mid];

    if (midV == target)	return mid;


    // L     M     R 
    // 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
    //
    if (leftV <= midV && midV <= rightV)
        return target < midV ? searchRotated_bs(nums, target, left, mid - 1) : searchRotated_bs(nums, target, mid + 1, right);
    else if (leftV >= midV && midV <= rightV)
        return target > midV && target <= rightV ? searchRotated_bs(nums, target, mid + 1, right) : searchRotated_bs(nums, target, left, mid - 1);
    else if (leftV <= midV && midV >= rightV)
        return target>=leftV && target<midV ? searchRotated_bs(nums, target, left, mid - 1) : searchRotated_bs(nums, target, mid + 1, right);
    else 
        return -1;
}
public:

// 33. Search in Rotated Sorted Array
int search(vector<int>& nums, int target)
{
    return searchRotated_bs(nums, target, 0, nums.size() - 1);
}

 

적당한 결과를 얻었다.