二分查找算法及其扩展

二分查找是面试中手写代码经常遇到的题目, 昨天还有同事说有个面试, 手写代码这一环节就是二分查找.
在下面两个版本的实现中, 假设传入的数组是递增的.

在面试的时候, 需要问清楚, 传入的数组的特点:

• 是否是排好序的
• 递增还是递减
• 当数字有重复时, 是否返回任意一个数的下标即可
• 同时, 查找时需要特别注意边界条件

二分查找实现起来不算难, 需要特别注意这些细节. 正是这些细节决定了你是否可以通过面试的这个环节.

Case 1: 二分查找一个数的下标, 当有多个目标数存在时,返回任意一个.

递归版本

int BinarySearch::search(const std::vector<int>& datas,
                         const int dest)
{
    LOG(INFO) << "Enter: " << __func__;
    int ret = -1; 
    ret = searchInternal(datas, 0, datas.size() - 1, dest);
    LOG(INFO) << "Leave: " << __func__;
    return ret;
}

int BinarySearch::searchInternal(const std::vector<int>& datas,
                                 const int startIndex,
                                 const int endIndex,
                                 const int dest)
{
    if (startIndex > endIndex)
    {   
        LOG(INFO) << "Not Found Dest: " << dest;
        return -1; 
    }   
    int mid = startIndex + (endIndex - startIndex) / 2;
    if (datas[mid] == dest)
    {   
        return mid;
    }   
    else if (datas[mid] > dest)
    {   
        return searchInternal(datas, startIndex, mid - 1, dest);
    }   
    else
    {   
        return searchInternal(datas, mid + 1, endIndex, dest);
    }   
}

非递归版本

只实现了internal方法

int BinarySearch::searchInternal(const std::vector<int>& datas,
                                 int startIndex,
                                 int endIndex,
                                 const int dest)
{
    int ret = -1; 
    while (startIndex <= endIndex)
    {   
        int midIndex = startIndex + (endIndex - startIndex) / 2;
        if (datas[midIndex] == dest)
        {   
            ret = midIndex; 
            break;
        }   
        else if (datas[midIndex] < dest)
        {   
            startIndex = midIndex + 1;
        }   
        else
        {   
            endIndex = midIndex - 1;
        }   
    }   
    return ret;
}

Case 2: 查找第一个大于或等于某个数的下标

算法思想: 等待查找失败,那么查找失败的最后一个区间的下一个元素, 即是满足条件的元素.
例如:
数组: 1 2 3 5 6 7
目标数: 4
查找区间的起始index和结束index的变化见下表

查找轮数	startIndex	endIndex
1	0	5
2	0	2
3	1	2
4	2	2
5	3	2

结束时, startIndex所指的即为满足条件的元素下标.
需要注意的是, 最后返回的时候,需要比较startIndex和最初endIndex的大小,如果 startIndex > endIndex, 说明查找失败,没有满足条件的元素.

实现

int BinarySearch::searchInternal(const std::vector<int>& datas,
                                 int startIndex,
                                 int endIndex,
                                 const int dest)
{
    int ret = -1; 
    int end = endIndex;
    while (startIndex <= endIndex)
    {   
        int midIndex = startIndex + (endIndex - startIndex) / 2;
        if (datas[midIndex] >= dest)
        {   
            endIndex = midIndex - 1;
        }   
        else
        {   
            startIndex = midIndex + 1;
        }   
    }   
    return startIndex <= end ? startIndex : -1; 
}

Case 3: 查找第一个大于某个数的下标

当中间下标数小于等于目标数时, 继续查找右边区间.
当中间下标数大于目标数时, 继续查找左边区间.
当startIndex > endIndex时, 结束查找, 此时startIndex所指的数字即为查找的数字下标, 如果startIndex大于起始endIndex则查找失败,返回 -1.

int BinarySearch::searchInternal(const std::vector<int>& datas,
                                 int startIndex,
                                 int endIndex,
                                 const int dest)
{
    int ret = -1; 
    int end = endIndex;
    while (startIndex <= endIndex)
    {   
        int midIndex = startIndex + (endIndex - startIndex) / 2;
        if (datas[midIndex] > dest)
        {   
            endIndex = midIndex - 1;
        }   
        else
        {   
            startIndex = midIndex + 1;
        }   
    }   
    return startIndex <= end ? startIndex : -1; 
}

扩展题型

扩展1: 查找数组中某个数的位置的最小下标, 没有则返回-1

思路参考Case 2. 先找到第一个大于或者等于目标数的数字, 判断该数字是否等于目标数, 如果等于目标数, 则返回该数字的下标, 否则返回-1.

扩展2: 查找数组中某个数的位置的最大下标, 没有则返回-1

思路参考Case 3. 先找到第一个大于目标数的数字, 判断该数字前面一个下标的数字是否等于目标数, 如果等于目标数, 则返回该数字的下标, 否则返回-1.

扩展3: 查找数组中小于某个数的最大下标, 没有返回-1.

思路参考Case 2. 先找到第一个大于或者等于目标数的数字, 然后判断前一个下标是否合法, 如果合法,则返回, 否则返回-1.

扩展4: 查找数组中某个数的出现次数

思路: 使用Case 2求出下界, 使用Case 3求出上界, 然后用上界 - 下界 即为某个数出现的次数.
但是需要注意返回值, 当越界时, 不能返回-1, 而是返回越界值来计算差值.

参考资料:
http://blog.csdn.net/yefengzhichen/article/details/52372407