11.3 给定一个排序后的数组，包含n个整数，但这个数组已被旋转很多次，次数不详。请编写代码找出数组中的某个元素。可以假定数组元素原先是按从小到大的顺序排序的。
解法：
可以直接从开始一个一个比较，也可以采用二分查找的方法。
在经典二分查找中，我们会将x与中间元素进行比较，以确定x属于左半部分还是右半部分。此题的复杂之处在于数组被旋转过，可能有一个拐点。
不过在左右两边至少有一边是有序的，因此我们可以看看按正常顺序排列的那一半数组，确定应该搜索左半部分还是右半部分。
但是如果左侧元素和中间元素完全相同，我们可以检查是否和左右边的元素相同，如果不同，说明左半部分是完全重复的元素，右半部分是升序排序的。但是如果和最右边元素相同，此时右半部分和左半部分都可能是有序或者重复的，因此需要两边都进行搜索。
C++实现代码：
#include<iostream>
using namespace std; int searchBinary(int a[],int left,int right,int x)
{
int mid=(left+right)/;
if(a[mid]==x)
return mid;
if(left>right)
return -;
//左半部分有序
if(a[left]<a[mid])
{
if( x>=a[left] && x<=a[mid])
return searchBinary(a,left,mid-,x);
else
return searchBinary(a,mid+,right,x);
}
else if(a[left]>a[mid])//右半部分有序
{
if(x>=a[mid]&&x<=a[right])
return searchBinary(a,mid+,right,x);
else
return searchBinary(a,left,mid-,x);
}
//可能左半部分有序也可能右半部分有序
else if(a[left]==a[mid])
{
if(a[mid]!=a[right])//左半部分全是重复的元素
return searchBinary(a,mid+,right,x);
else //有可能左半部分也可能右半部分都死重复的元素
{
int result=searchBinary(a,left,mid-,x);
if(result==-)
return searchBinary(a,mid+,right,x);
else
return result;
}
}
return -;
}
int search(int a[],int n,int x)
{
return searchBinary(a,,n-,x);
} int main()
{
int arr[]={,,,,,,,,,};
cout<<search(arr,,)<<endl;
}