学步园

折半查找应该算是算法中比较简单常见，但却很实用的方法之一了，又叫做二分搜索，其应用比较广泛，可以用于排序数组中元素的查找，复杂度仅为log（N），也可以用于有序数组中插入元素等等，一般而言针对排序数组的一些算法都会活多或少的用到折半查找活折半查找的思想，折半查找的实现主要分为两种方式，一种是遍历非递归形式，一种是采用递归的形式。

1、非递归形式，这种实现主要是通过每次调整中点的位置来实现。

int binsearch1(int arr[], int k, int l, int h){
        if(l > h){
                return -1;
        }
        int mid;
        while(l <= h){
                mid = (l + h) / 2;
                if(k == arr[mid]){
                        return mid;
                }else if(k > arr[mid]){
                        l = mid + 1;
                }else{
                        h = mid - 1;
                }
        }
        return -1;
}

这种方式比较灵活，而已有利于解决很多变形的问题，后面会介绍。

2、递归的形式，这种形式比较简单，调整起点，中点，终点的位置，递归函数就可以实现

int binsearch2(int arr[], int k, int l, int h){
        if(l > h){
                return -1;
        }
        int mid = (l + h) / 2;
        if(k == arr[mid]){
                return mid;
        }else  if(k > arr[mid]){
                binsearch2(arr, k, mid +1, h);
        }else if(k < arr[mid]){
                binsearch2(arr, k, l, mid - 1);
        }
        return -1;
}

二、现在考虑复杂一点的二分搜索的问题，当我们遇到这样的数组a={1, 2, 3, 3, 5, 7, 8}，存在重复的元素，需要从中找出3第一次出现的位置，这里3第一次出现的位置是2，《编程珠玑》里给出了很好的分析，二分搜索主要的精髓在于不变式的设计（就是上面的while循环条件式）。

int binsearch_first(int arr[], int k, int n){
        int l = -1, h =  n;
        while(l + 1 != h){
                int m = (l + h) / 2;
                if(k > arr[m]){
                        l = m;
                }else{
                        h = m;
                }
        }
        int p = h;
        if(p >= n || arr[p] != k){
                return -1;
        }
        return h;
} 

int binsearch_last(int arr[], int k, int n){
        int l = -1, h =  n;
        while(l + 1 != h){
                int m = (l + h) / 2;
                if(k >= arr[m]){
                        l = m;
                }else{
                        h = m;
                }
        }
        int p = l;
        if(p <= -1 || arr[p] != k){
                return -1;
        }
        return p;
}

int split(int a[], int n)
{
    for (int i=0; i<n-1; i++) {
        if (a[i+1] < a[i])
            return i;
    }
    return -1;
}

int bsearch_rotate(int a[], int n, int t)
{
    int p = split(a, n); //找到分割位置
    if (p == -1)
        return bsearch_first(a, n, t); //如果原数组有序，则直接二分查找即可
    else {
        int left = bsearch_first(a, p+1, t); //查找左半部分
        if (left == -1) {  //左半部分没有找到，则查找右半部分
            int right = bsearch_first(a+p+1, n-p-1, t); //查找右半部分
            if (right != -1) return right+p+1;  //返回位置，注意要加上p+1
            return -1;
        }
        return left; //左半部分找到，则直接返回
    }
}

还有另外一种方法就是还按照一次二分查找的形式进行，可以这样考虑计算数组中点的时候，会将数组分为两个部分，一部分是有序的，或者两部分有序的，总之必然有一遍是有序的，那么就又可以按照二分的思想进行求解。

二分查找算法有两个关键点：1）数组有序；2）根据当前区间的中间元素与x的大小关系，确定下次二分查找在前半段区间还是后半段区间进行。

仔细分析该问题，可以发现，每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。

a[mid]分别与a[left]和a[right]比较，确定哪一段是有序的。

如果左边是有序的，若x<a[mid]且x>a[left], 则right=mid-1；其他情况，left =mid+1；

如果右边是有序的，若x> a[mid] 且x<a[right] 则left=mid+1；其他情况，right =mid-1；

代码如下：

int bsearch_rotate(int a[], int n, int t)
{
    int low = 0, high = n-1;
    while (low <= high) {
        int mid = low + (high-low) / 2;
        if (t == a[mid])
            return mid;
        if (a[mid] >= a[low]) { //数组左半有序
            if (t >= a[low] && t < a[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {       //数组右半段有序
            if (t > a[mid] && t <= a[high])
                low = mid + 1;
            else
                high = mid - 1;
        }   
    }   
    return -1; 
}

四、有序数组的插入问题

其实有序数组的插入问题也可以通过二分搜索实现，只是返回值不同而已，在没找到元素的时候返回l（最左值）值就是元素应该插入的位置。

int binsearch1(int arr[], int k, int l, int h){
        if(l > h){
                return -1;
        }
        int mid;
        while(l <= h){
                mid = (l + h) / 2;
                if(k == arr[mid]){
                        return mid;
                }else if(k > arr[mid]){
                        l = mid + 1;
                }else{
                        h = mid - 1;
                }
        }
        return l;
}

五、二分思想的变形，其实二分是一种思想，不单单是应用于有序序列，可以应用于很多将序列进行划分的问题上，例如：

给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数；

这道题看上去和二分完全没有关系，但是却可以利用二分的思想去解决，就是通过位将所有的元素分为两个集合，每次选取元素个数小的集合再按位分为两部分，最后找到不在文件中的32位数元素。

参考：二分查找之谜题

《编程珠玑》