二分搜索总结

对于二分搜索，一般的程序员都不陌生了，大部分都会认为是小菜一碟了，其实不然，据《编程珠玑》上说，这个算法的第一篇论文1946年就发表了，但是第一个没有错误的二分程序再1962年才出现，所以相信，对于这个算法，大家即使烂熟于心，但是如果没有亲自动手写过，还是会出现不少问题的。现在就按照自己的理解来总结。

有一个有序整数数组，给定一个整数，请从数组中找出这个整数出现的位置，如果这个整数出现多次，返回其中一个位置。

最基本的二分搜索程序

int binary_search(int arr[], int start, int end, int elem) {
    int left, right, mid;

    if(start > end || arr[start] > elem || arr[end] < elem) {
        return -1;
    }

    left = start;
    right = end;
    while(left <= right) {
        mid = left + (right - left) / 2;
        if(arr[mid] < elem) {
            left = mid + 1;
        } else if(arr[mid] > elem) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

上面的代码中需要注意的是mid = left + (right - left) / 2这行代码，很多程序中都会使用mid = (right + left) / 2这样的代码，但是如果right和left值比较大，它们的和就有可能溢出，虽然溢出的情况很少，但是为了增加代码的健壮性，还是应该选择使用mid = left + (right - left) / 2这样的方式来求mid。

基本二分搜索程序的改进

以上的基本二分搜索函数中，while循环内部当arr[mid] == elem时进行了两次比较，下面的程序将对此进行改进，代码如下：

int binary_search_updated(int arr[], int start, int end, int elem) {
    int left, right, mid;
    left = start;
    right = end;
    while(left + 1 < right) {
        mid = left + (right - left) / 2;
        if(arr[mid] <= elem) {
            left = mid;
        } else {
            right = mid;
        }
    }
    if(arr[left] == elem) {
        return left;
    } else {
        return -1;
    }
}

在上面的改进的二分搜索程序中，while循环内每次循环仅比较一次就可以给left，right赋值，whle循环结束的条件是left + 1 < right，所以当arr[mid] > elem时，right = mid，如果此时right = mid - 1，那么就有可能使得程序最终进入死循环，如left = 2， right = 3时，mid = (right + left) / 2=2，此时再次将2赋值给left，这样就进入死循环了，所以在a[mid] > elem时就使得right = mid；而while退出的条件是left + 1 = right。

有重复元素的二分搜索

如果有序数组中有重复的元素，上面的函数依然有效，可以返回其中一个元素，但是如果需要返回指定的元素的第一次出现或者是最后一次出现，那该怎么写代码呢？一个很直接的思路就是找到与给定值相等的元素之后，再顺序向前遍历找第一个，或者向后遍历找最后一个，但是这样的方法增加了比较的次数，具体可以看看这篇博文（博主是网易杭研院的MySQL数据库开发人员）： http://hedengcheng.com/?p=595。当在数组中找到与给值相等的元素之后，可以继续使用二分查找找到第一次出现的位置或最后一次出现的位置。

先看看如果有重复元素，找出最后一次出现的位置，则对上面binary_search_updated()函数需要做一点点改进，代码如下：

/*找出有序数组arr中值等于给定值的元素的序号，如果有多个元素满足条件，
则返回其中序号最大的那个元素
*/

int binary_search_dup_max(int arr[], int start, int end, int elem) {
    int left, right, mid;
    left = start;
    right = end;
    while(left + 1 < right) {
        mid = left + (right - left) / 2;
        if(arr[mid] <= elem) {
            left = mid;
        } else {
            right = mid;
        }
    }
    if(arr[right] == elem) {
        return right;
    }else if(arr[left] == elem) {
        return left;
    } else {
        return -1;
    }
}
 

while循环执行完成之后，先判断right处的元素是否等于elem，如果是则这个元素就是最大的，否则就看left处的元素是否等于elem，如果等于，那么就返回left值，否则就没有找到，看看这个数组[1，2， 2， 3， 4， 4， 4， 5， 6， 7， 7]，要从数组中找到最右边的4的位置。对于这个数组，第一次计算mid值为5（(0 + 10) / 2），此时arr[5] == elem， 那么left = 5， right = 10，第二次计算mid值为7， arr[7] = 5 > elem，那么right = mid = 7，第三次计算mid = 6，arr[6] == elem，那么left = 6，此时left + 1 = right，所以while循环结束，由于此时arr[right] == 5，不等于elem，而arr[left] == 4 == elem，所以返回left。

在while循环后，为什么要先判断right处的值是否为elem呢？如果要找的这个元素是数组中最大值，则就是最后一个元素，那么在整个查找的过程中，right值都不会改变，且它始终指向最右边的那个元素，所以在while循环执行完之后要先判断right处的值是否为elem。

如果要找出重复元素的第一次出现的位置，则可以对上面的程序进行简单的修改即可。但是如果要根据传入的参数来查找到底是要找重复元素第一次出现的位置，还是最后一次出现的位置，则在比较arr[mid]与elem大小时，则要单独考虑arr[mid]与elem相等时，left与right的值，代码如下：

/*
 * flag表示找重复元素的第一次出现还是最后一次出现，如果flag为0，则表示找第一次出现，如果flag为1，则表示找最后一次出现
 */
int binary_search_duplicated(int arr[], int start, int end, int elem, int flag) {
    int left, right, mid, res;
    left = start;
    right = end;
    while(left + 1 < right) {
        mid = left + (right - left) / 2;

        if(arr[mid] < elem) {
            left = mid + 1;
        } else if(arr[mid] > elem){
            right = mid - 1;
        } else {
            if(flag == 0) {
                right = mid;
            } else {
                left = mid;
            }
        }
    }
    if(flag) {
        if(arr[right] == elem) return right;
        else if(arr[left] == elem) return left;
    } else {
        if(arr[left] == elem) return left;
        else if(arr[right] == elem) return right;
    }
    return -1;
}

上面的代码中，使用flag标志来表示是找第一次出现的位置，还是找最后一次出现的位置，当arr[mid]与elem相等时，则需要根据flag的值来决定是移动left指针，还是right指针，如果flag==0，那么就是要找第一次出现的位置，此时应该给right赋值为mid，如果flag == 1，就是要找最后一次出现的位置，此时应该给left赋值为mid，最后while循环执行完成后，还要根据flag的值来返回对应的位置。

Reference

《编程珠玑》第二版第4章，第九章

《编程之美》第3章，3.11节

何登成的技术博客： http://hedengcheng.com/?p=595