[고전 면접 문제] 정렬 된 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.

[제목]
한 배열 의 맨 처음 몇 개의 요 소 를 배열 의 끝 에 옮 기 는 것 을 우 리 는 배열 의 회전 이 라 고 부른다.정렬 된 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 {3, 4, 5, 1, 2} 은 {1, 2, 3, 4, 5} 의 회전 이 고 이 배열 의 최소 값 은 1 이다.
[분석]
이 문제 의 가장 직관 적 인 해법 은 결코 어렵 지 않다.처음부터 끝까지 배열 을 한 번 훑 어보 면 가장 작은 요 소 를 찾 을 수 있 고 시간 복잡 도 는 분명히 O (N) 이다.그러나 이 사 고 는 입력 배열 의 특성 을 이용 하지 않 았 기 때문에 우 리 는 더 좋 은 해법 을 찾 을 수 있 을 것 이다.
 우 리 는 회전 한 후의 배열 이 실제 적 으로 두 개의 정렬 된 하위 배열 로 나 눌 수 있 고 앞의 하위 배열 의 요 소 는 모두 뒷 면 배열 의 요소 보다 크 거나 같다 는 것 을 알 게 되 었 다.우 리 는 또한 가장 작은 원소 가 바로 이 두 개의 하위 그룹의 경계선 이라는 것 을 알 수 있다.우 리 는 이원 탐색 법의 사고방식 으로 이 가장 작은 원 소 를 찾 으 려 고 한다.
    우 리 는 배열 중간 에 있 는 요 소 를 얻 었 다.이 중간 요소 가 앞의 증가 서브 배열 에 있다 면 첫 번 째 포인터 가 가리 키 는 요소 보다 크 거나 같 아야 합 니 다.이 때 배열 에서 가장 작은 요 소 는 이 중간 요소 의 뒤에 있어 야 합 니 다.우 리 는 첫 번 째 지침 을 이 중간 요 소 를 가리 키 면 찾 는 범 위 를 좁 힐 수 있다.마찬가지 로 중간 요소 가 뒤의 증가 서브 배열 에 있다 면 두 번 째 포인터 가 가리 키 는 요소 보다 작 거나 같 아야 합 니 다.이 배열 에서 가장 작은 요 소 는 이 중간 요소 의 앞 에 있어 야 합 니 다.우 리 는 두 번 째 지침 을 이 중간 요 소 를 가리 키 면 찾 는 범 위 를 좁 힐 수 있다.우 리 는 이어서 업 데 이 트 된 두 개의 지침 으로 새로운 중간 요 소 를 얻 고 비교 하 며 순환 했다.
【 코드 】

/*********************************
*     ：2015-01-04
*     ：SJF0115
*     :                ，           
*     ：
**********************************/
#include <iostream>
using namespace std;

int SearchMin(int A[],int n){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    //     
    if(A[end] > A[start]){
        return A[start];
    }//if
    //     
    //     
    while(start <= end){
        int mid = (start + end) / 2;
        // [start,mid]  [mid,end]  
        if(A[mid] > A[start]){
            start = mid;
        }
        // [start,mid]  [mid,end]  
        else if(A[mid] < A[start]){
            end = mid;
        }
        else{
            return A[mid+1];
        }
    }//while
}

int main(){
    int A[] = {2,3,4,5,6,7,8};
    cout<<SearchMin(A,7)<<endl;
    return 0;
}