二分查找谜题

唉。微软的面试就挂在了二分查找的相关问题上，当时脑袋抽风，今天在论坛上又看到了一道关于二分查找的问题，结果还是稀里糊涂的，遂决定还是把二分查找相关的问题总结成文，以便自己查看。

我们先来扯扯正常的二分：二分查找通过持续跟踪数组中包含的元素target的范围来解决问题。一开始，这个范围是整个数组；然后通过target与数组的中间项进行比较并抛弃一半的范围来缩小范围，该过程持续进行，直到在数组中找到target或者包含target的范围为空为止。所以，在有n个元素的数组中，二分查找大概需要log n次的操作。需要指出的是，使用二分查找的前提是 1.数组 2.元素有序。二分查找的实现主要有两种方式，一种是循环非递归的方式，另一种是递归的方式。这两种形式的代码如下：

/**
     * 循环非递归
     */
    public static int binSearch(int[] arr, int l, int h, int key) {
        if (l > h) {
            return -1;
        }
        int mid = 0;
        while (l <= h) {
            mid = ((l + h) >> 1);
            if (arr[mid] > key) {
                h = mid - 1;
            } else if (arr[mid] == key) {
                return mid;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 递归方式
     */
    public static int binSearchRec(int[] arr, int l, int h, int key) {
        if (l > h) {
            return -1;
        }
        int mid = (l + h) >> 1;
        if (key < arr[mid]) {
            binSearchRec(arr, l, mid - 1, key);
        } else if (key > arr[mid]) {
            binSearchRec(arr, mid + 1, h, key);
        } else {
            return mid;
        }
        return -1;
    }

以上是标准的二分的思路，今天在bbs看到的题目是这样的：

已知有序数组a[N]， 从中间某个位置k（k未知，k=-1表示整个数组有序）分开，然后将前后两部分互换，得到新的数组，在该新数组的查找元素x。如：a[]={1,2,3,4,5,6,7,8,9,10}，从k=4分开，得到新数组a={10 9 8 7 1 2 3 4 5 6}。

看到这道题目初始的想法是先找到划分的临界点（这里是1），然后再在划分点的左边或者右边二分查找x。

实现的代码如下：这里在第二次二分的时候使用了Java里Arrays提供的二分查找的方法，需要注意的是Arrays.binarySearch中第二的参数的下标是包含在二分查找的数组里的，而第三个参数的下标是不包含在里的。（类似与String.substring方法）

public int getIndexOfTarget(int[] num, int target){
        int minIndex = getMin(num);
        System.out.println(minIndex);
        if(target < num[0]){
            return Arrays.binarySearch(num, minIndex, num.length, target);
        }else{
            return Arrays.binarySearch(num, 0, minIndex, target);
        }
    }
    public int getMin(int[] num){
        int start = 0;
        int end = num.length - 1;
        int middle = start;
        while(num[start] >= num[end]){
            if(end - start == 1){
                return end;
            }
            middle = (start + end) / 2;
            if(num[middle] <= num[end]){
                end = middle;
            }else if(num[middle] >= num[start]){
                start = middle;
            }
        }
        return middle;
    }

但是题目的要求是只进行一次二分查找。。。

仔细分析该问题，可以发现，每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。可以利用这个特性，在一次二分的过程中增加判断过程来求解。

public int binary_search_in_rotate_array(int num[], int x) {
        int low = 0;
        int high = num.length - 1; // 注意上界
        while (low <= high) {
            int mid = low + ((high - low) >> 1); // 可防止溢出；移位操作高效；
            if (num[mid] == x)
                return mid;
            if (num[mid] >= num[low]) {// 左半段有序
                if (x < num[mid] && x >= num[low]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else { // 右半段有序
                if (x > num[mid] && x <= num[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1; // 找不到，则返回-1
    }