검 지 offer (6) --- 회전 수조 의 최소 숫자

제목: 한 배열 의 처음에 몇 개의 요 소 를 배열 의 끝 에 옮 겨 서 우 리 는 배열 의 회전 이 라 고 부른다.정렬 되 지 않 은 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 {3, 4, 5, 1, 2} 은 {1, 2, 3, 4, 5} 의 회전 이 고 이 배열 의 최소 값 은 1 이다.NOTE: 제 시 된 모든 요 소 는 0 보다 큽 니 다. 배열 크기 가 0 이면 0 을 되 돌려 주 십시오.
제목 분석: 이 문 제 는 매우 간단 한 방법 이 있 습 니 다. 원래 비 체감 서열 이 었 기 때문에 회전 한 후에 가장 작은 요 소 를 찾 아야 합 니 다. 사실은 머리 에서 현재 위치 수가 뒷 위치 수 보다 많 으 면 뒷 위치 수 는 반드시 최소 수 입 니 다.그러나 이러한 시간 복잡 도 는 O (n) 이다. 더욱 효율 적 인 방법 을 찾기 위해 서 는 2 분 으로 찾 는 것 이다. 이러한 사건 의 복잡 도 는 O (logn) 밖 에 없다.

C++  ：
class Solution {
public:
    int minNumberInRotateArray(vector<int> arr)
    {
        /*     O(n)
        int size=rotateArray.size();
        if(size==0) return 0;
        for(int i=0;irotateArray[i+1])
            {
                return rotateArray[i+1];
            }
        }
        return rotateArray[0];
    }
    */
        //          O(nlogn)
        if(arr.size()==0) 
            return 0;
        int high=arr.size()-1;
        int low=0;
        while(lowint mid=(high-low)/2+low;
            if(arr[mid]>arr[high])          
            {
                low=mid+1;
            }
            else if(arr[mid]==arr[high])  //         111110001    
            {
                high=high-1;             //          
            }
            else
                high=mid;
        }
        return arr[low];
    }

};