して回転

Question

私は最近、次のようであるプログラミングの問題に直面した：

ソートされた配列が与えられ、配列はいくつかの未知の点で回転させて、私が見つけなければなりませんその中の最小要素。配列には重複も含めることができます。例えばのために

：

Input: {5, 6, 1, 2, 3, 4} 

Output: 1 

Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} 

Output: 0 

私はシンプルなソリューションを踏襲し、完全な配列を谷と最小値を求めるトラバースすることです。この解は時間O（n）を必要とします。最小要素はそれより前の要素が大きい要素であるという事実を理解しています。そのような要素が存在しない場合、回転はなく、最初の要素が最小になります。

しかし、私はO（Logn）ソリューションを求められました。 O（Logn）時間にそれを解決する方法はありますか？私の頭の上オフ

Answer 1

：

• 注最初のエントリ
• バイナリ検索を実行します。ピボット要素が格納されている第1の要素よりも大きいか等しい場合には右半分を選択し、ピボット要素が小さい場合は左半分を選択します。 {4,5,6,7,1,2,3}与え
例えば

、：>47で

• ピボット、左半分1に減らし、2 < 4で右半分に{1,2,3}
• ピボットを減らします。
• 1つの要素のみを考慮すると、回答は1です。

Answer 2

これを参照してください。 ソートされた配列なので、ピボットを見つけるためにバイナリ検索を適用する必要があります。

最も小さい要素は、配列がピボットされた場所です。

コールこのfindpivot(arr,0,n-1);

int findPivot(int arr[], int low, int high) 
{ 
    // base cases 
    if (high < low) return -1; 
    if (high == low) return low; 

    int mid = (low + high)/2; /*low + (high - low)/2;*/ 
    if (mid < high && arr[mid] > arr[mid + 1]) 
    return mid; 
    if (mid > low && arr[mid] < arr[mid - 1]) 
    return (mid-1); 
    if (arr[low] >= arr[mid]) 
    return findPivot(arr, low, mid-1); 
    else 
    return findPivot(arr, mid + 1, high); 
}