二分查找上界和下界

2015-06-26

@(笔试面试)

在算法题里面,最常用的算法也就是二分查找,以及二分查找的变种,时间效率高,而且占用常量空间.但是二分查找也有一个问题,需要查找的数列必须是有序的,不然需要提前进行排序的.
关于查找一个元素是否在数列内,这样的算法是比较基础的了,较为复杂的是含有重复元素的时候怎么办?

一般的二分查找

先举一个例子,一个给定一个有序数组,查找是否存在一个元素.

int BinarySearch_basic(vector<int> &nums,int target)
{
    int len = nums.size();
    if(len == 0)
        return -1;
    int low = 0;
    int high = len -1;
    while(low <= high)
    {
        int mid = (low +  high) >>1;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

算是经典的二分查找程序了,每一次都折半查找空间,直到遇到相等的元素,返回该元素的下标,否则,查找范围不对其了,返回-1.
二分查找相对顺序查找的一个重要的优点就是减少了比较次数,比较次数正是查找算法复杂度的关键,减少查找次数就是降低时间复杂度.

二分查找寻找下界

上面的例子很简单,没有重复的元素,但是若序列中有重复的元素,那就不能简单的返回其中一个下标了,用户需要的是返回重复元素的起始下标和终止下标,用来表示范围,同时还要保证在不存在的情况下的鲁棒性.
先是利用二分查找寻找下界:
相对于基本的二分查找,一个重要的不同是,就是在找到相同的元素的时候,不能直接返回其下标地址,还需要不断的移动上边界,直到查找范围不能满足条件,下面是我的代码:

int findLower(const vector<int> &nums, int target)
{
    if(nums.size() < 1)
        return -1;
    int low = 0;
    int high = nums.size() -1;
    while(low <= high)
    {
        int mid = (low + high)>>1;
        if(nums[mid] >= target)
            high = mid - 1;
        else
            low = mid +1;
    }
    if(low < nums.size() && nums[low] == target)
        return low;
    else
        return -1;
}

简单的介绍一下:当中间元素大于或者等于目标元素的时候,都需要用mid-1来替换查找上界,结束的条件是high<low,这时候需要检查是否满足条件;

若low已经超过序列的长度,则肯定是不存在的(high没有移动,若存在的话,high至少移动一次!),那么越界呢?high是一直在降低的,所以也可能变成-1,为什么不见查呢?这里不需要特别的处理,因为所有的元素都是大于或者等于目标元素值的,是否存在,只需要下面一个检查条件.
若low没有越界,则从下标为low开始,元素值都是大于或者等于目标元素值的,这是检查low位置的元素值,若与目标元素值相等,则low就是下界位置,否则是不存在元素的.

二分查找寻找上界

查找上界与查找下界非常相似,唯一的不同是,当找到相同的元素的时候,要移动的是查找下界,查找下界变大,直到查找范围不满足条件.
下面是我的代码:

int findUpper(const vector<int> &nums, int target)
{
    if(nums.size() < 1)
        return -1;
    int low = 0;
    int high = nums.size() - 1;
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        if(nums[mid] <= target)
            low = mid + 1;
        else
            high = mid -1;
    }
    if(high > -1 && nums[high] == target)
        return high;
    else
        return -1;
}

当遇到相等的元素,查找范围的下界都用mid+1替换,这样下界不断的增大,直到low>high.这时候也需要检查条件:

若存在相同的元素,应该是low向上移动的,所以,在存在元素的情况下,是不可能high变成-1的(low没有移动),这种越界情况下是不存在元素的,所以返回-1,那么low呢?跟上面的情况类似了,需要看high位置的元素了.
在high没有低于下界的情况下,此时low位置前面的元素肯定是小于或者等于目标元素的.此时high正好在low前面的一个位置,只需要检查这个位置的元素,若与目标元素相等,则上界就是high了,否则,其他的元素更不满足了(递增),返回-1.

其他

还有一种应用,就是给定一个序列,有序,给定一个值,寻找第一个比这个值大的元素的位置,或者比该元素小的最大的那个数值的位置.
这个题目是上次我面试的时候遇到的,文章已经详细的描述了.
本文寻找上下界的方法也可以用于求解该问题,但是缺点是,若不存在的话就不好找了,需要稍微对前面两个方法修改.

比如,第一个比目标值大的元素的位置:

int func1(const vector<int> &nums, int target)
{
    if(nums.size() < 1)
        return -1;
    int low = 0;
    int high = nums.size() - 1;
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        if(nums[mid] <= target)
            low = mid + 1;
        else
            high = mid -1;
    }
    return low;
}

可能所有的元素都比目标值小,上面的程序返回的是序列的最后一个元素的下一个位置,若需要返回-1的话,需要稍微修改一下最后一句就好了.

比目标元素小的最大的值的位置:

int func2(const vector<int> &nums, int target)
{
    if(nums.size() < 1)
        return -1;
    int low = 0;
    int high = nums.size() -1;
    while(low <= high)
    {
        int mid = (low + high)>>1;
        if(nums[mid] >= target)
            high = mid - 1;
        else
            low = mid +1;
    }
    if(low < nums.size() && nums[low] == target)
        return high;
}

若素有的元素都比目标元素大,则实际上返回的是序列第一个元素的前面的一个位置,也就是-1,所以不用修改了.