http://hi.baidu.com/nicker2010/item/4d4f71145532a234b83180a7

總結規律，簡化模型

題目都不難，重要的是很敏銳的發現問題的規律。

旋轉有序數組的二分搜索,如
int?arr[N]?=?{15,16,19,20,25,1,3,4,5,7,10,14};
查找X?=?5

主要思想：

每次根據L和R求出M后，M左邊[L,?M]和右邊[M+1,?R]這兩部分中至少一個是有序的。

arr[M]和X比較

(1).?arr[M]==X，返回M

(2).?arr[M]?<?arr[R]，說明右側有序，當?arr[M]<X<arr[R]，則L=M+1,否則R=M-1

(3).?arr[M]?>?arr[L]，說明左側有序，當?arr[L]<X<arr[M]，則R=M-1,否則L=M+1

簡單代碼：

int?CirculateBSearch(const?int*?arr,int?N,int?x)
{
????int?L=0,R=N-1,M;
????while(L?<=?R)
????{
????????M?=?(L+R)>>1;
????????if(arr[M]?==?x)?return?M;
????????if(arr[M]?<=?arr[R])//arr[M]右側是有序的
????????{
????????????if(arr[M]<x?&&?x<=arr[R])//x在有序部分的內部
????????????????L?=?M+1;
????????????else?R?=?M-1;
????????}
????????else//arr[M]左側是有序的
????????{
????????????if(x<arr[M]?&&?arr[L]<=x)//x在有序部分的內部
????????????????R?=?M-1;
????????????else?L?=?M+1;
????????}
????}
????return?-1;
}

簡單測試：

????const?int?N?=?12;
????int?X?=?5;
????int?arr[N]?=?{15,16,19,20,25,1,3,4,5,7,10,14};
????cout<<"Array?:?";
????PrintArray(arr,N);
????int?index?=?CirculateBSearch(arr,N,X);
????if(index?<?0)?cout<<X<<"?is?not?found?in?arr.\n";
????else?cout<<X<<"?is?found?in?arr,?index?=?"<<index<<endl;

總結

以上是生活随笔為你收集整理的旋转有序数组的二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。