[LeetCode] Search in Rotated Sorted Array

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int mid, left=0, right=nums.size();
        
        int start = nums[0];
        int pivot = 0;
        
        if(nums.size()<3){
            for(int i=0; i<nums.size();i++)
            {
                if(target == nums[i])
                    return i;
            }
            return -1;
        }
        
        
        while(left<right){
            mid=left+(right-left)/2;
            
            if(nums[mid]>=start){
                left=mid+1;
            }
            else if(nums[mid]<start){
                right=mid;
            }
            
        }
        pivot =left;

        
        if(start>target){
            left = pivot;
            right = nums.size();
        } else{
            right = pivot;
            left = 0;
        }
        
        while(left<=right){
            mid=left+(right-left)/2;
            
            if(nums[mid]<target){
                left=mid+1;
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
            else if(target == nums[mid]){
                return mid;
            }
        }
        return -1;
    }
};

승선이형이 추천해줬던 문제였는데, 계속 통과가 안돼서 잠깐 잊고 살았었다. 역시 오랜만에 보면 또 보이는 게 다른 것 같다.
문제를 푸는 방법 자체는 이미 알아낸 상태였다.
오름차순이 바뀌기 시작하는 지점을 먼저 이분탐색으로 찾아 pivot으로 설정, 가장 처음에 있는 수와 target을 비교하여 결과에 따라 pivot의 오른쪽 or 왼쪽을 이분탐색으로 탐색하여 target 수가 있는지 확인하는 방법으로 풀었다.

문제는 pivot인덱스를 찾을 때 비교에 따라 left, right를 어떻게 설정하는지였는데, nums[mid]가 start랑 같을 때를 고려하지 않았던 것과 right 와 left 를 모두 mid-1, mid+1 로 설정되도록 해서 생략돼버리는 부분이 생기는 것이 오류의 원인이었다.

솔직히 살짝 때려맞추기 느낌도 있었고, nums의 크기가 3보다 작을 때는 buffer-overflow가 발생하는 걸 그냥 예외로 빼서 따로 처리한 것이 조금 코드를 난잡하게 만드는 것 같기도 하다.
아직 탐색에서 인덱스가 변화는 것을 세세하게 생각하는데에는 어려움이 있는 것 같다.