[Leetcode] 33. Search in Rotated Sorted Array 문제 풀이

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

Search in Rotated Sorted Array - LeetCode

문제 내용

정렬된 배열이 rotate되어 있다.

rorate 되어 있는 배열에서 값 찾는 문제

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

 

문제 풀이

binary search 로 풀 수 있는 데 생각해야 되는 문제이다.

rotate가 되어 있기 때문에

binary search 사용할 때 조건이 추가된다.

 

rotate이 되면 첫번째 값이 마지막보다 무조건 크게 설정된다.

중간 값이 2가지 경우가 있다.

1. target보다 중간값이 작거나 target이 마지막 값이 큰 경우
2. target이 중간값보다 크거나 target이 시작 값보다 작을 경우

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int s = 0;
        int e = nums.size()-1;
        while(s <= e) {
            int m = (s+e)>>1;
            if (nums[m] == target)
                return m;
            else if (nums[s] < nums[e]) {
                auto it = lower_bound(nums.begin()+s, nums.begin()+e+1, target);
                return (it != nums.end() && *it == target) ? it-nums.begin() : -1;
            } 
            else if (nums[m] < nums[e]) {
                if (target < nums[m] || target > nums[e]) {
                    e = m-1;
                } else {
                    s = m+1;
                }
            }
            else {
                if (target > nums[m] || target < nums[s]) {
                    s = m+1;
                } else {
                    e = m-1;
                }
            }
        }
        
        return -1;
    }
};