二分查找

简介

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

其实我们小时候就用过这个算法，只是没注意罢了，比如一本书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

/*给定一个有序(不降序)数组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

/*给定一个有序(不降序)数组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

/*给定一个有序(不降序)数组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

/*给定一个有序(不降序)数组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

/*给定一个有序(不降序)数组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页

下期预告

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