关于二分查找(Binary Search)及其变种形式的总结

二分查找是基本算法,但是据统计只有10%的程序员可以写出没有bug的代码。出错的原因主要集中在对边界值得选择和判定条件上,一不小心就可能导致超出边界或者死循环的情况。这里作如下总结:

标准版二分查找:
在有序(非降序)数组中查找一个target值,数组中元素没有重复,找到target则返回该元素对应的index,找不到则返回-1。

注意1:如果是start < end,那么当target等于num[num.length-1]时,会找不到该值。 注意2:因为num[mid] > target, 所以如果有num[index] == target, index一定小于mid,能不能写成end = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成end = mid,当循环到start = 0, end = 0时(即num[start] = 1, num[end] = 1时),mid将永远等于0,此时end也将永远等于0,陷入死循环。也就是说寻找target = -2时,程序将死循环。

注意3:因为num[mid] < target, 所以如果有num[index] == target, index一定大于mid,能不能写成start = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。也就是说寻找target = 9时,程序将死循环。

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //注意2
        }
        else{
            start = mid + 1; //注意3
        }
    }
    return -1;
}

二分查找变形一:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最小值,找不到则返回-1。

注意1:为了对左右相邻的两个数进行对比,循环结束的时候,start和end应该相隔1。

注意2:a). 当num[mid] == target时,此时并不能直接返回mid,因为有可能num[mid-1]或者num[mid-2]…也等于target,所以此时应该将end  = mid,然后继续循环。b). 当num[mid] > target时,如果有num[index] == target,那么index一定小于mid,本来按此道理应该令end = mid – 1,但是为什么此处可以end = mid呢?回头去看上一题(标准版)的注意2,只有当start = end时,才会出现死循环的情况。这里因为while循环的限制条件使得start和end永远不可能相等,所以end = mid也是正确的。由此,我们可将a) 和 b) 两种情况合并。

注意3:这里与上题一致,不用有变化。但是在这里写成start = mid也是成立的,为啥呢?回头看上题的注意3,同样的例子num = {1, 2, 5, 7, 9}; 在上题中,如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。但在此题中由于while中的限制条件的变化,避免了这种死循环的发生。

注意4:此处为什么要分别检验num[start]和num[end]是否等于target呢?因为这两个值都有可能等于target,取决于中间二分时start和end的更新过程。这里随便用几个简单的例子即可验证。如果循环结束时num[start] == num[end] == target,根据题意应该返回start,所以我们先验证start。如果两个值都不是target,则target不存在,返回-1。

public int binarySearchMinimumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意2
            end = mid;
        }
        else{
            start = mid + 1; //注意3
        }
    }
    if(num[start] == target) //注意4
        return start;
    else if(num[end] == target)
        return end;
    else
        return -1;
}

二分查找变形二:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最大值,找不到则返回-1。

道理与上一题相同,只要在注意2和注意3处与上题反过来就行了,原理不重复了,拿不准的时候可以用几个简单的test case测试一下。

public int binarySearchMaximumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){ //注意2
            start = mid;
        }
        else{
            end = mid - 1; //注意3
        }
    }
    if(num[end] == target)
        return end;
    else if(num[start] == target) //注意4
        return start;
    else
        return -1;
}

二分查找变形三:
在有序(非降序)数组中查找一个可能的”最大”index,使得num[index] < target,数组中元素可能有重复,找不到则返回-1。

注意1:我们可以对此步分开考虑,当num[mid] == target时,因为我们要求num[index] < target,所以index必须在mid左边。当num[mid] > target时,target肯定在num[mid]的左边,所以index肯定也要在mid的左边。那么再多想一步,假如num[mid] >= target时,我们进行了end = mid的操作,会产生什么后果呢?经我的有限测试,好像并没有什么问题,因为while中的限制条件导致了每当start + 1 == end的时候,循环就结束了,所以标准版二分查找中出现的死循环的情况并不存在。

注意2:当num[mid] < target时,为什么此处用start = mid而不是start = mid + 1?因为有可能num[mid+1] == target,此时如果start = mid + 1, 则num[start] == target,明显错过了正解。

public int binarySearchClosestFromLeft(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意1
            end = mid - 1;
        }
        else{ //注意2
            start = mid;
        }
    }
    if(num[end] < target){
        return end;
    }
    else if(num[start] < target){
        return start;
    }
    else{
        return -1;
    }
}

二分查找变形四:
在有序(非降序)数组中查找一个可能的”最小”index,使得num[index] > target,数组中元素可能有重复,找不到则返回-1。
道理与上题完全相同,稍作调整即可。

注意1:此处同上题注意1原理相同,写成start = mid也应该没有问题。

public int binarySearchClosestFromRight(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){
            start = mid + 1; //注意1
        }
        else{
            end = mid;
        }
    }
    if(num[start] > target){
        return start;
    }
    else if(num[end] > target){
        return end;
    }
    else{
        return -1;
    }
}

综上所述,总结规律:
1. 当数组中没有重复元素时:while循环判定条件是(start <= end),每次start更新为mid + 1,end更新为mid – 1。
2. 当数组中含有重复元素时或者要找的值是target的相邻数时,判定条件是(start + 1 < end),当num[mid] == target时,并不返回mid,而是根据情况跟新start或者end。每次start更新为mid,end也更新为mid即可。

Advertisements

One thought on “关于二分查找(Binary Search)及其变种形式的总结

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s