软协面试时候某部长问的二分查找究竟是什么?

想必大家在今年软协面试的时候都被某个魔鬼面试官问过一个问题:什么是二分查找?

那么,究竟什么是二分查找呢?二分查找的优势是什么呢?二分查找怎么判断边界条件呢?二分查找有什么变种呢?

ps:本文纯萌新文,给2020级新生做个科普,尽量写的非常的简洁

什么是二分查找

先简单看一道例题吧:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

解法一:暴力搜索

我们从头开始访问这个升序数组,如果遍历时我们在这个数组里访问到了和target相同的值,那么我们就返回他的数组下标。如果一直循环到数组结束都没有与target匹配的相同的值,那么就返回-1。

具体代码如下:

public static int TraversalSearch(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target)
            return i;
        //由于是升序数组,我们可以加一个判断条件来提前结束循环
        if (nums[i]>target)
            break;
    }
    return -1;
}

看似没有问题,但是我们仔细想一想一个例子:

nums = {1, 2, 4, 5}target = 6 的时候,我们需要遍历整个数组,直到遍历到最后一个我们发现没有和target相同的值,最后返回-1。

这么做的时间复杂度是 O(n) ,最坏的情况下我们需要将整个数组进行遍历,比较消耗时间。这个时候,二分查找就出来啦!

解法二:二分查找

二分查找的思路是:

  • 如果目标值等于中间元素,则找到目标值。
  • 如果目标值较小,继续在左侧搜索。
  • 如果目标值较大,则继续在右侧搜索。

我们的题目条件是升序数组,也就是说,数组已经进行了排序。那么我们先寻找数组最中间的值mid,我们首先去对比中间值的大小,如果 target>mid ,那么我们就去搜索从mid分开的数组右侧,否则就去搜索数组左侧。

二分查找的非递归代码如下:

public int BinarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        if (target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

举例:当 nums = {1, 2, 3, 4, 5, 6, 7}target = 6 的时候,我们先找到 num[mid] = 4 这个数值与
target 进行对比,由于是升序数组,那么 target 必然在数组中间的右边,所以我们将原本的数组
nums[0, nums.length-1] 区间缩小为 nums[mid, nums.length-1] ,然后搜索到 nums[mid] = 6 ,发现与 target 匹配,故返回下标6。

二分查找的优势

那么二分查找的优势在哪呢?还是看上面的例子,如果我们使用暴力搜索,我们需要对比6次才能返回结果,而使用二分查找,我们只进行了2次对比。

二分查找的时间复杂度为 O(log_2n) ,相比于遍历的时间复杂度 O(n) ,明显就快了很多。

以上是小白科普时间

二分查找的边界问题

{1,2,3,3,3,4,5} 这个例子中,我们的目标值如果为3,那么二分查找到的数组下标为3,也就是最中间那个数。那如果我想返回最先出现的下标,也就是下标2,或者最后出现的下标,比如下标4,那么我们需要收缩查找。

搜索左侧边界

我们在搜索的时候,想要返回左侧边界,则需要收缩右侧的搜索范围,即当我们遇到 nums[mid] == target 时,不要马上返回结果,而是继续收缩查找区间,将右侧的区间缩小,使得 right = mid-1 ,此时我们再次判断 left <= right 条件进入循环判断,如果 left == right ,那么 mid == left ,即搜索左侧;如果 left <= right ,$right$收缩区间,直到 $mid == left$。

如果一直没有搜索到 target ,有两种情况:

  • target 比数组里所有的数都大,此时 l = mid +1 不断执行,那么最后会出现 l == n 的情况,此时我们应该返回-1
  • target 比数组里所有的数都小,此时 r = mid -1 不断执行,那么最后会出现 r == -1 的情况,但是由于我们是判断左侧区间,也就是说 ① target 的下标是0,$nums[mid] == target$ 执行 r = mid - 1 ;② target 比所有元素都小, nums[mid] > target 执行 $r = mid - 1$;此时如果单纯判断 r == -1 ,则无法分辨①和②两种情况,因此我们需要用 nums[l] != target 判断。

非递归代码如下:

public int LeftBinarySearch(int[] nums, int target) {
    int n = nums.length;
    int l = 0;
    int r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target)
            r = mid - 1;
        else if (nums[mid] > target)
            r = mid - 1;
        else if (nums[mid] < target)
            l = mid + 1;
    }
    if (l > n - 1 || (nums[l] != target))
        return -1;
    return l;
}

搜索右侧边界

与左侧搜索同理,我们需要收缩左侧的搜索范围。我们只需要对上面的代码进行一些微调就可以了。

如果一直没有搜索到 target ,有两种情况:

  • target 比数组里所有的数都大,此时 l = mid +1 不断执行,那么最后会出现 l == n 的情况,但是由于我们是判断右侧区间,也就是说 ①$target$的下标是 n-1nums[mid] == target 执行$l = mid + 1$;② target 比所有元素都小,$nums[mid] > target$ 执行 l = mid + 1 ;此时如果单纯判断 r == n ,则无法分辨①和②两种情况,因此我们需要用 nums[r] != target 判断。
  • target 比数组里所有的数都小,此时 r = mid -1 不断执行,那么最后会出现 r == -1 的情况,此时我们应该返回-1。

非递归代码如下:

public int RightBinarySearch(int[] nums, int target) {
    int n = nums.length;
    int l = 0;
    int r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target)
            l = mid + 1;
        else if (nums[mid] > target)
            r = mid - 1;
        else if (nums[mid] < target)
            l = mid + 1;
    }
    if (r < 0 || (nums[r] != target))
        return -1;
    return r;
}
3赞

怎么不是用C语言写的呀,有点看不太懂欸

那同学你学到指针了吗(滑稽)

额,我刚学完C语言的函数那一章

0

粤 ICP 备 2020080455 号