# 循环有序数组中的二分查找 Search in a rotated sorted array

1、可以用它来查找某一个数

2、可以用于查找某一个范围。如《二分查找有序数组中某个数的所在范围 Search for a Range》。

3、可以用它来查找两个有序数组的中位数。

4、本文中，二分查找又多了一项新的本领，可以用它在循环有序数组中查找某个数。

``````class Solution {
public:

int search(int A[], int n, int target)
{
if(n<=0)
return -1;
int left = 0, right = n-1;
while(left<=right)
{
int mid = left + ((right-left)/2);
if(A[mid] == target)
return mid;

if(A[left] <= A[mid])//转折点在右半边
{
if(A[left] <= target && target < A[mid])
right = mid - 1;
else
left = mid + 1;
}
else //转折点在左半边
{
if(A[mid] < target && target <= A[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}

};``````

``````class Solution {
public:
bool search(int A[], int n, int target) {
return bisearch(A, 0, n-1, target);
}

bool bisearch(int A[], int left, int right, int target)
{
if(left > right)
return false;
int mid = left + (right - left)/2;
if(target == A[mid])
return true;
// A[left], A[mid], A[right]
// 1 3 5
if(A[mid] > A[left] && A[mid] < A[right]) //普通二分
{
if(target < A[mid])
return bisearch(A, left, mid-1, target);
else
return bisearch(A, mid+1, right, target);
}
// 5 1 3
else if(A[mid] < A[left] && A[mid] < A[right]) //转折在左侧
{
if(target > A[mid] && target <= A[right])
return bisearch(A, mid+1, right, target);
else
return bisearch(A, left, mid-1, target);
}
// 3 5 1
else if(A[mid] > A[left] && A[mid] > A[right]) //转折在右侧
{
if(target < A[mid] && target >= A[left])
return bisearch(A, left, mid-1, target);
else
return bisearch(A, mid+1, right, target);
}
// 3 3 3
else //只有这种左中右都相等的情况下没有办法判断
{
return bisearch(A, left, mid-1, target) || bisearch(A, mid+1, right, target);
}

}

};
``````