之前咱们说过二分法的适用范围是排序好的数组。但其实在实际应用中，数组未必一定要是严格排序的递增、或者递减的。

这里说一个例子：rotated sorted array

排序好的数组，在某一点被切断，前后两个部分交换位置，我们叫他rotated sorted array。

比如说size为n的sorted的array A[]，其中A[0] < A[1] < … A[n-1]。我们在index i上把这个array分成2分部，并且前后交换位置。

数组A[]就变成了:

A[i], A[i+1], … A[n-1], A[0],A[1], … A[i-1]

这个数组的排序被打乱了。这样还能用二分法搜索吗？答案是可以的。因为他尽管整体不是严格递增递减，但在某一个区间还是排序好的。所以如果我们能够确定要搜索的对象在哪个区间，就还是可以使用二分法搜索。

那么怎么确定刷哪个区间呢？我们先通过观察边界来找到搜索区间。

我们还设left = 0, right = n-1:

如果一个数x比最左边的数大 （比如上面的例子，最左边是A[i], 比他大的包括A[i+1]到A[n-1]），我们可知从left到x是sorted的。反之，x如果比left小 （同样看上面的例子，比left小的包括从A[0] 到 A[i-1]），我们可知从x到right是sorted。具体算法：

while ( left <= right){

mid = (left + right)/2;

if (num == A[mid]) return mid;

if (A[mid] > A[left]){ // 从left到mid是sorted的

if (num >= A[left] && num < A[mid]) right = mid – 1; // num在[left, mid)区间，丢掉右边

else left = mid + 1;

}else { // 从mid到right是sorted

If (num <= A[right] && num > A[mid]) left = mid + 1; // num 在(mid, right]区间，丢掉左边

else right = mid – 1;

}

}

return -1;

通过上面的例子，我们可以看到二分法搜索不一定非要是严格排序好的。在很多并不严格排序的地方、或者排序被打乱的情况下，比如上面的例子，一样可以使用。甚至有的时候完全没有排序，也可以用来解决一些特定的问题。这个具体的例子以后有机会再说。