leetcode 문제 라 이브 러 리 - 회전 정렬 배열 검색

제목 설명:
오름차 순 으로 정렬 된 배열 이 미리 알 수 없 는 한 점 에서 회전 했다 고 가정 합 니 다.
배열  [0,1,2,4,5,6,7]  이 가능 하 다, ~ 할 수 있다,...  [4,5,6,7,0,1,2]  )。
주어진 목표 값 을 검색 합 니 다. 배열 에 이 목표 값 이 존재 하면 색인 을 되 돌려 줍 니 다. 그렇지 않 으 면 되 돌려 줍 니 다.  -1  。
너 는 배열 에 중복 되 는 요소 가 존재 하지 않 는 다 고 가정 할 수 있다.
당신 의 알고리즘 시간 복잡 도 는 반드시 O(log n) 등급.
예시 1:

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

예시 2:

  : nums = [4,5,6,7,0,1,2],
target = 3
  : -1

방법: 2 분 검색

class Solution {
public:
    int search(vector& nums, int target) {
        if(nums.size()==0) return -1;
        int low,mid,high;
        low=0;high=nums.size()-1;
        
        while(low=nums[low]){//     
                if(nums[mid]>target&&nums[low]<=target)//      
                    high=mid-1;
                else low=mid+1;
            }
            else{//     
                if(nums[mid]<=target&&nums[high]>=target)//      
                    low=mid+1;
                else high=mid-1;
            }
        }
        if(low==high&&nums[low]==target) return low;
        return -1;
    }
};

생각:
제목 요구 복잡 도 log (n)따라서 가장 유력 한 방법 은 2 분 검색 입 니 다. 그러나 주어진 숫자 서열 순서 가 회전 하기 때문에 판단 할 때 mid 왼쪽 이 냐 오른쪽 이 냐 를 주의해 야 합 니 다. 목표 값 이 왼쪽 이 냐 오른쪽 이 냐 를 판단 해 야 합 니 다. 목표 값 이 질서 있 는 쪽 에 있어 야 전통 적 인 2 분 방법 을 사용 할 수 있 습 니 다. 즉, 중간 값 이 목표 값 보다 크 면 하 이 = mid - 1 또는 중간 값 이 항목 보다 큽 니 다.표시 값 이 작 으 면 low = mid + 1.