二分查找

简介

二分查找作为高效的查找算法，可以说是每个学计算机的都应该懂的，在每年的面试中，可以说是必须考察的点；

其实我们小时候就用过这个算法，只是没注意罢了，比如一本书300页，你要找第100页，你翻到了第20页，那么你肯定向后翻，你又翻到了第80页，你肯定继续向后找，每次砍掉一些。还比如英语字典，是按照单词的字典序排列的，你也是利用上面的算法在找。其实这就是二分查找。

适用范围

有序的线性表（一定得是数组存储的，由于需要快速取得对应位置的值）

需要注意的问题

int binarySearch(int arr[], int beg, int end, int target)

1、安全性检测

• beg 与 end 必须>=0
• beg <= end

• end <= 数组的大小
  对应的检测语句如下：

  assert(beg >= 0 && beg <= end && end < sizeof(arr)/sizeof(int)); /*sizeof这个语法貌似不一定对*/
  

2、特殊判断
如何出入的是一个空数组，此时beg==end==0,计算mid会得0，然后访问arr[0]会报错所以应该加一句：

    if (beg == end && beg == 0)
        return -1;

3、注意mid的求法：

/*method1:*/ int mid = (beg + end) / 2;
/*method2:*/ int mid = beg + (end - beg) /2 ;
/*method3:*/ int mid = beg + ((end - beg) >> 1);

方法1：存在溢出的风险例如0x02 0x7fffffff
方法2、方法3：对于现代的编译器，两者执行效率应该一样；
注意：加法的优先级大于右移，所以需要在>>操作加括号(掉过坑，冏)
在何的博文中有一个网友提到的(beg + end)/2的语意是向0取整而不是向下取整，比如（-3 + 2）/ 2 == 0的，而beg + (end - beg) / 2是向下取整则为-1
4、循环的结束条件
循环和递归程序应注意的三点：1、初始条件；2、转换条件；3、终止条件；
对于二分需要注意的是终止条件情况比较复杂，可以利用画图来描述
beg———-mid————end
beg <= mid <= end 是天然成立的
分类讨论：
arr[mid] < target 说明目标值在mid的右边
arr[mid] == target 恰好等于目标值
arr[mid] > target 目标值在mid的左边
最终结束条件（除随机选择一个与目标值相等的需求）是beg == end 或者beg + 1 == end刚好在临界点，判断条件一般是while (beg + 1 < end)可以避免死循环

分类(参考编程之美)

给定一个有序(不降序)数组arr，求解任意一个i使得arr[i]等于v，不存在则返回-1

    int findEqual(int arr[], int beg, int end, int target)
    {
        assert(0 <= beg && beg <= end);
        int mid = -1;
        int ret = -1;
        while (beg <= end)
        {
            mid = beg + ((end - beg)>>1);
            if (arr[mid] == target)
            {
                ret = mid;
                break;
            }else if (arr[mid] > target){
                end = mid - 1;
            }else {
                beg = mid + 1;
            }
        }
        return ret;
    }

给定一个有序(不降序)数组arr，求解最小的i使得arr[i]等于v，不存在则返回-1

    int findMinEqual(int arr[], int beg, int end, int target)
    {
        assert(0 <= beg && beg <= end);
        int mid = -1;
        int ret = -1;
        while (beg <= end)
        {
            mid = beg + ((end - beg)>>1);
            if (arr[mid] == target)
            {
                if (mid - 1 >= 0 && arr[mid - 1] == target)
                    end = mid - 1;
                else{
                    ret = mid;
                    break;
                }
            }else if (arr[mid] > target){
                end = mid - 1;
            }else {
                beg = mid + 1;
            }
        }
        return ret;
    }

给定一个有序(不降序)数组arr，求解最大i使得arr[i]等于v，不存在则返回-1

    int findMaxEqual(int arr[], int beg, int end, int target)
    {
        assert(0 <= beg && beg <= end);
        int mid = -1;
        int ret = -1;
        while (beg <= end)
        {
            mid = beg + ((end - beg)>>1);
            if (arr[mid] == target)
            {
                if (mid + 1 <= end && arr[mid + 1] == target)
                {
                    beg = mid + 1;
                }else{
                    ret = mid;
                    break;
                }
            }else if (arr[mid] > target){
                end = mid - 1;
            }else {
                beg = mid + 1;
            }
        }
        return ret;
    }

给定一个有序(不降序)数组arr，求解最大i使得arr[i]小于v，不存在则返回-1

    int findMaxLess(int arr[], int beg, int end, int target)
    {
        assert(0 <= beg && beg <= end);
        int mid = -1;
        while (beg + 1 < end)
        {
            mid = beg + ((end - beg)>>1);
            if (arr[mid] >= target)
            {
                end = mid - 1;
            }else{
                beg = mid;
            }
        }
        if (arr[end] < target)
            return end;
        else if (arr[beg] < target)
            return beg;
        else
            return -1;
    }

给定一个有序(不降序)数组arr，求解最小i使得arr[i]大于v，不存在则返回-1

    int findMinGreat(int arr[], int beg, int end, int target)
    {
        assert(0 <= beg && beg <= end);
        int mid = -1;
        while (beg + 1 < end)
        {
            mid = beg + ((end - beg)>>1);
            if (arr[mid] <= target)
                beg = mid + 1;
            else
                end = mid;
        }
        if (arr[beg] > target)
            return beg;
        else if (arr[end] > target)
            return end;
        else
            return -1;
    }
    /*别人的写法*/
    int findOther(int arr[], int beg, int end, int target)
    {
        int mid = -1;
        while (beg <= end)
        {
            mid = beg + (end - beg) / 2;
            if (arr[mid] <= target)
                beg = mid + 1;
            else
                end = mid - 1;
        }
        if (arr[beg] <= target)
            return -1;
        else
            return beg;
    }

一些不常见的写法

引用貌似得翻墙

声明

由于水平有限，若发现错误请告知，共同进步；

参考

1、二分查找(Binary Search)需要注意的问题，以及在数据库内核中的实现
2、编程之美p261页

下期预告

字符串专题，欢迎继续支持