vlambda博客
学习文章列表

算法面试题——二分查找套路法

本文引用了Leetcode第704、744、69、35、278题


二分查找是算法课上必修的查找方法,二分查找算法的思想很容易理解,但是实现中的一些细节问题让人很挠头:

面试官:看看这道题吧,给你这个排好序的数组[1, 2, 2, 2, 3, 6],2就是target,找到2这个元素,任何一个2都可以。

我:(心中暗喜,二分查找嘛哈哈),blah blah。。。

面试官:不错不错,那我把条件改一下,让你找到最后一个比2小的元素呢?

我:呃呃,那我把我代码的条件改一下哈。。。

(十分钟后)

我:呃呃,怎么死循环了呢,我再改改。。。

(又十分钟后)

面试官:没事儿没事儿,回去等通知吧。

二分查找,看似容易,但是一旦开始要处理细节问题,就麻烦不断,要么死循环,要么返回的不是正确的值。

我也为此头疼了很长一段时间,但终于发现了一套做二分查找的“套路”,只要套进去,基本没有搞不定的情形。

废话不说,开始“套路”。


算法面试题——二分查找套路法
四步套路法

拿到一道二分查找问题,要分为这四步思考:

  1. 问题抽象化:这道题的要求是要找到哪个target?还是要找到第一个比target小(或小于等于)的元素?还是第一个比target大(或大于等于)的元素?

  2. 如果当前mid指向的值等于target了之后,我应该怎么处理?是直接return?还是移动left或者right?

  3. 最后一次循环的时候(循环是以left <= right作为判断条件),left === right,那么这个时候,我是移动left还是移动right,移动之后,是left指向的我想返回的结果,还是right?

  4. 没找到怎么办?



算法面试题——二分查找套路法
最基本的二分查找

在分析二分查找变形题目之前,我们先来看看最最基本,大家都能熟练做出的二分查找题。这里我用Leetcode的第704题:二分查找,作为例子:

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

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

答案很经典:

/** * @param {number[]} nums * @param {number} target * @return {number} */var search = function(nums, target) { let left = 0, right = nums.length-1; while (left <= right) { let mid = left + ((right - left) >> 1); if (nums[mid] === target) return mid; if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } } return -1;};

计算mid的时候,使用left + ((right - left) >> 1),而不是(right + left) >> 1,是为了防止溢出问题。

从上面,我们可以得到一个模板:

// 问题1:问题抽象化var search = function(nums, target) { let left = 0, right = nums.length-1; while (left <= right) { let mid = left + ((right - left) >> 1);// 问题2:如果当前mid指针等于target了之后,我应该怎么处理? 替换:(是否需要提前退出?)if (nums[mid] === target) return mid; if (替换:(等号条件放在right?)nums[mid] > target) { right = mid - 1; } else if (替换:(等号条件放在left?)nums[mid] < target) { left = mid + 1; } } // 问题4:没找到怎么办? // 问题3:最后一次循环的时候,left === right,那么这个时候,我是移动left还是移动right,移动之后,是left指向的我想返回的结果,还是right? 替换:(没找到怎么办) return 替换:(返回left还是right,还是-1?)-1;};

根据不同的题目,以及我们对问题1、2、3、4的答案,我们只要把替换部分替换成问题的答案,就可以解决二分查找的变形问题。

下面看几道Leetcode真题实践一下。



算法面试题——二分查找套路法
寻找比target大的最小元素

我们看下Leetcode的第744题:寻找比目标字母大的最小字母:

给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子,如果目标字母target = 'z' 并且有序数组为 letters = ['a', 'b'],则答案返回 'a'。

示例:
输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"

输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"

输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"

输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"

输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"

输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"

注:
letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成,最少包含两个不同的字母。
目标字母target 是一个小写字母。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

我们先回答上面那四个问题:

1. 答案很简单:寻找比target大的最小元素

2. 当前mid指针等于target了之后,因为我要找的是比target大的最小元素,因此我要向右、向更大的元素寻找,因此要移动left。那么,nums[mid] === target这种情况应该归给left移动的条件中。

3. 最后一次循环的时候,left === right,如果数组中存在这样的值,此时left和right都指向的正好比mid大的那个元素(已经指向了正确答案啊),那么这个时候,我是移动left还是移动right呢?因为此时mid也是指向第一个比target大的元素,那么应该是移动right了。移动之后,是left指向正确答案,因此最后要返回left。如果数组中不存在这样的值,此时,left和right指向数组中最后一个元素,还是会移动left,这种情况会在第4步处理。

4.没找到怎么办?这道题里面,如果最后的left比输入数组的长度还要大的话,那么就返回第一个元素(这是题目的要求)。

好了,代码如下:

/** * @param {character[]} letters * @param {character} target * @return {character} */var nextGreatestLetter = function(letters, target) { let asciiT = target.charCodeAt(0); let left=0, right = letters.length-1; while (left <=right) { let mid = left + ((right - left) >> 1); if (letters[mid].charCodeAt(0) > asciiT) { right = mid-1; } else if (letters[mid].charCodeAt(0) <= asciiT) { left = mid+1; } } if (left > letters.length-1) return letters[0]; return letters[left];};

是不是超级简单?

那再看一道题。



算法面试题——二分查找套路法
寻找比target小的最大元素

我们来看Leetcode的第69题:x的平方根:

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

我们先回答上面那四个问题:

1. 答案很简单:寻找比target小的最大元素,不过如果找到了target,就直接返回target

2. 当前mid指针等于target了之后,因为我要找的是比target小的最大元素,因此我要向左、向更小的元素中寻找,因此要移动right。不过,这道题当中,nums[mid] === target这种情况直接就可以退出了,不需要归属left或者right 。

3. 最后一次循环的时候,left === right,此时left和right都指向的正好比mid小的那个元素(这就是正确答案)。那么这个时候,我是移动left还是移动right呢?因为此时mid是指向第一个比target小的元素,那么应该是移动left了。移动之后,是right指向正确答案,因此最后要返回right。

4. 没有不存在的情况

/** * @param {number} x * @return {number} */var mySqrt = function(x) { let left = 1, right = x; while (left <= right) { let mid = left + ((right - left) >> 1); let square = mid * mid; if (square === x) { return mid; } if (square > x) { right = mid - 1; } else if (square < x) { left = mid + 1; } } return right;};

是不是so easy!

类似的还有Leetcode第35题:搜索插入位置。唯一的区别就是这道题需要返回right + 1。不过这道题也可以当做“寻找比target大的最小元素”来做,其实更简单。

下一题!



算法面试题——二分查找套路法
寻找第一个等于target的元素

我们看下Leetcode第278题:第一个错误的版本:

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-bad-version
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

还是回答上面那四个问题:

1. 我们要寻找比第一个等于target的元素的index

2. 当前mid指向的值等于target了之后,因为我要找的第一个等于target的元素,因此我要向左寻找,因此要移动right。相等的情形归于right的条件下。

3. 最后一次循环的时候,left === right,此时left和right都指向的正好比mid小的那个元素(因此即使遇到了第一个等于target的元素,你也不知道这是不是第一个,会迫使right继续向左移动),那么这个时候,因为mid指向的第一个比target小的元素,那么应该是移动left了。移动之后,是left指向正确答案,因此最后要返回left。

4.没找到怎么办?这道题里面,肯定会存在第一个错误版本,所以不用单独处理这个问题。

代码如下:

/** * Definition for isBadVersion() * * @param {integer} version number * @return {boolean} whether the version is bad * isBadVersion = function(version) { * ... * }; */
/** * @param {function} isBadVersion() * @return {function} */var solution = function(isBadVersion) { /** * @param {integer} n Total versions * @return {integer} The first bad version */ return function(n) { let left = 1,right = n; while(left <= right) { let mid = left + ((right - left) >> 1); if (isBadVersion(mid)) { right = mid - 1; } else { left = mid + 1; } } return left; };};

不过瘾?再来一个!



寻找最后一个等于target的元素

不多说了,代码如下:

let left = 0,right = nums.length-1; while(left <= right) { if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] <= target) { left = mid + 1; } } return right;}

你能理解为什么这么做么?