[Leetcode] 33. Search in Rotated Sorted Array - binary search

1. 문제링크

Search in Rotated Sorted Array - LeetCode

- You must write an algorithm with O(log n) runtime complexity.

라고 되어있으면 binary search 해야한다는 뜻이다.

 

 

2. 범위 생각하기, 포인터를 변경해야 되는 조건 생각하기

l, r포인터를 두고 m을 구한다.

 

1) nums[L] ~ nums[M]이 오름차순 일 때

[4, 5, 6, 7, 8, 1, 2] = nums

 L          M         R

위 경우는 nums[L] ~ nums[M]까지는 오름차순이다.

 

그럼 먼저 L포인터를 M+1의 위치로 변경해야하는 경우를 생각해보자.

target이 8인 경우(target > nums[m])와

target이 1인 경우(target < nums[l])인 경우가 되겠다.

 

위 조건에 해당되지 않는다면 R 포인터를 M-1로 이동해준다.

 

 

2) nums[L] ~ nums[M]이 오름차순이 아닐 때 (rotated)

[4, 5, 6, 0, 1, 2, 3] = nums

 L          M         R

 

R포인터를 변경할 조건은

target < nums[M] (target : 6)이거나

target > nums[R] (target : 5)인 경우이다.

 

그 외에는 L포인터르 변경해준다.

 

3. solution

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int res = -1;
        int l = 0, r= nums.size()-1;
        while(l <= r){            
            int m = (l + r) / 2;
            if(nums[m] == target){
                return m;            
            }
            if(nums[l] <= nums[m]){
                if(target > nums[m] || target < nums[l])
                    l = m+1;
                else
                    r = m-1;
            } else {
                if(target < nums[m] || target > nums[r])
                    r=m-1;
                else
                    l=m+1;
            }
        }
        return res;
    }
};