本文共 898 字，大约阅读时间需要 2 分钟。

总结规律，简化模型

题目都不难，重要的是很敏锐的发现问题的规律。

旋转有序数组的二分搜索,如

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;

转载地址：http://zveti.baihongyu.com/