1. （严格递增序列）旋转数组的元素查找

 简单来说分为三种情况进行分析

1. 整个旋转数组单调递增

根据x和A[mid]的大小关系，更迭范围。

        // 1. 整个旋转数组单调递增if (A[left]<A[right]){if (A[mid] == x)return mid;else if (x < A[mid])right = mid-1;else if (x > A[mid])left = mid+1;}

2. 旋转数组分为两个递增序列，mid位于第一个递增序列当中

mid将旋转数组分为两块区间，但第一块区间的值的条件并不是简单的x<A[mid]，因为小于A[mid]的元素还有可能为最下面的区间，如图。

        // 2. 旋转数组分为两个递增序列，mid位于第一个递增序列当中if (A[mid]>A[left]){if (x == A[mid])return mid;else if (x<A[mid] && x >= A[left]){right = mid-1;}else{left = mid+1;}}

 3. mid位于第二个递增序列当中

        // 3. 旋转数组分为两个递增序列，mid位于第二个递增序列当中if (A[mid]<A[left]){if (x == A[mid])return mid;else if (x>A[mid] && x<=A[right]){left = mid+1;}else {right = mid-1; }}

最后的总代码：

#include <cstdio>const int N= 1e5+10;
int A[N];
int n,x;
int binary_search(int A[],int left,int right,int x){int mid;while (left < right){mid = left + (right-left)/2;// 1. 整个旋转数组单调递增if (A[left]<A[right]){if (A[mid] == x)return mid;else if (x < A[mid])right = mid-1;else if (x > A[mid])left = mid+1;}// 2. 旋转数组分为两个递增序列，mid位于第一个递增序列当中if (A[mid]>A[left]){if (x == A[mid])return mid;else if (x<A[mid] && x >= A[left]){right = mid-1;}else{left = mid+1;}}// 3. 旋转数组分为两个递增序列，mid位于第二个递增序列当中if (A[mid]<A[left]){if (x == A[mid])return mid;else if (x>A[mid] && x<=A[right]){left = mid+1;}else {right = mid-1; }}}if (A[left]==x)return left;return -1;
}
int main(){scanf("%d%d",&n,&x);for (int i=0;i<n;i++)scanf("%d",&A[i]);printf("%d",binary_search(A,0,n-1,x));return 0;}

2.（非递减序列）旋转数组的元素查找

思路一致，由于会出现重复的元素，因此，对寻找第一个x的寻找条件进行修改即可。

不过由于非递减的条件不好写，因此我们可以用else来表示

#include <cstdio>const int N= 1e5+10;
int A[N];
int n,x;
int binary_search(int A[],int left,int right,int x){int mid;while (left < right){mid = left + (right-left)/2;// 2. 旋转数组分为两个非递减序列，mid位于第一个非递减序列当中if (A[mid]>A[left]){if (x == A[mid])right = mid;else if (x<A[mid] && x >= A[left]){right = mid-1;}else{left = mid+1;}}else if (A[mid]<A[left]){// 3. 旋转数组分为两个递增序列，mid位于第二个递增序列当中if (x == A[mid])right=mid;else if (x>A[mid] && x<=A[right]){left = mid+1;}else {right = mid-1;}}else {//1. 整个旋转数组非递减if (A[mid] == x)right = mid;else if (x < A[mid])right = mid-1;else if (x > A[mid])left = mid+1;}}if (A[left]==x)return left;return -1;
}
int main(){scanf("%d%d",&n,&x);for (int i=0;i<n;i++)scanf("%d",&A[i]);printf("%d",binary_search(A,0,n-1,x));return 0;}

3. 旋转数组的最小值，通过数组左端元素判断最小值出现的位置

两个代码相同。需要注意 A[left] == A[mid] 的情况，最小值在右侧区间中

#include <cstdio>const int N= 1e5+10;
int A[N];
int n;
int binary_search(int A[],int left,int right){int mid;while (left < right){mid = left + (right-left)/2;// 1. 整个旋转数组单调递增if (A[left]<A[right]){return A[left];}// 2. 旋转数组分为两个单调递增序列，mid位于第一个单调递增序列当中if (A[mid]>A[left]){left = mid+1;}else if (A[mid]<A[left]){// 3. 旋转数组分为两个递增序列，mid位于第二个递增序列当中right = mid;}else if(A[mid]==A[left]){// A[left] == A[mid] 的情况，最小值在右侧区间中left = mid+1;}//printf("%d,%d\n",left,right);}return A[left];
}
int main(){scanf("%d",&n);for (int i=0;i<n;i++)scanf("%d",&A[i]);printf("%d",binary_search(A,0,n-1));return 0;}

4. 旋转数组的中位数

#include <cstdio>const int N= 1e5+10;
int A[N];
int n;
int binary_search(int A[],int left,int right){int mid;while (left < right){mid = left + (right-left)/2;// 1. 整个旋转数组单调递增if (A[left]<A[right]){return left;}// 2. 旋转数组分为两个单调递增序列，mid位于第一个单调递增序列当中if (A[mid]>A[left]){left = mid+1;}else if (A[mid]<A[left]){// 3. 旋转数组分为两个递增序列，mid位于第二个递增序列当中right = mid;}else if(A[mid]==A[left]){// A[left] == A[mid] 的情况，最小值在右侧区间中left = mid+1;}//printf("%d,%d\n",left,right);}return left;
}
int main(){scanf("%d",&n);for (int i=0;i<n;i++)scanf("%d",&A[i]);int minpos = binary_search(A,0,n-1);//printf("%d",minpos);if (n%2==0){printf("%.1f",(A[(minpos+n/2)%n]+A[(minpos+n/2)%n-1])/2.0);}else {printf("%.1f",A[(minpos+n/2)%n]/1.0);}return 0;}

 重点在于后面中位数的求解

    if (n%2==0){printf("%.1f",(A[(minpos+n/2)%n]+A[(minpos+n/2)%n-1])/2.0);}else {printf("%.1f",A[(minpos+n/2)%n]/1.0);}