算法通关手册

算法通关手册：06 数组二分查找

2021-12-23  本文已影响0人  ITCharge
06 数组二分查找.png

1. 算法介绍

「二分查找算法（Binary Search Algorithm）」，也叫做 「折半查找算法」、「对数查找算法」。是一种在有序数组中查找某一特定元素的搜索算法。

基本算法思想：先确定待查找元素所在的区间范围，在逐步缩小范围，直到找到元素或找不到该元素为止。

二分查找算法的过程如下所示：

举个例子来说，给定一个有序数组 [0, 1, 2, 3, 4, 5, 6, 7, 8]。如果我们希望查找 5 是否在这个数组中。

于是我们发现，对于一个长度为 9 的有序数组，我们只进行了 3 次查找就找到了我们需要查找的数字。而如果是依次遍历数组，则最坏情况下，我们需要查找 9 次。

整个查找过程的示意图如下所示：

image

2. 算法思想

二分查找算法是经典的 「减而治之」 的思想。

这里的 「减」 是减少问题规模的意思，「治」 是解决问题的意思。「减」 和 「治」 结合起来的意思就是 「排除法解决问题」。即：每一次查找，排除掉一定不存在目标元素的区间，在剩下可能存在目标元素的区间中继续查找。每一次通过一些条件判断，将待搜索的区间逐渐缩小，以达到「减少问题规模」的目的。而于问题的规模是有限的，经过有限次的查找，最终会查找到目标元素或者查找失败。

3. 简单二分查找

下面通过一个简单的例子来讲解下二分查找的思路和代码。

3.1 题目大意

给定一个升序的数组 nums，和一个目标值 target，返回 target 在数组中的位置，如果找不到，则返回 -1。

3.2 解题思路

利用二分查找算法进行解题。

设定左右节点为数组两端，即 left = 0，right = len(nums) - 1，代表待查找区间为 [left, right]（左闭右闭）。

取两个节点中心位置 mid，先比较中心位置值 nums[mid] 与目标值 target 的大小。

2.3 解题代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        # 在区间 [left, right] 内查找 target
        while left <= right:
            # 取区间中间节点
            mid = (left + right) // 2
            # 如果找到目标值，则直接返回中心位置
            if nums[mid] == target:
                return mid
            # 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
            elif nums[mid] < target:
                left = mid + 1
            # 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
            else:
                right = mid - 1
        # 未搜索到元素，返回 -1
        return -1

4. 二分查找细节

从上面的例子中我们了解了二分查找的思路和具体代码。但是真正在解决二分查找题目的时候还是需要考虑很多细节的。比如说以下几个问题：

  1. 区间的开闭问题：区间应该是左闭右闭，还是左闭右开？
  2. mid 的取值问题：mid = (left + right) // 2，还是 mid = (left + right + 1) // 2？
  3. 出界条件的判断：left <= right，还是 left < right？
  4. 搜索区间范围的选择：left = mid + 1、right = mid - 1、 left = mid、right = mid 应该怎么写？

下面一一讲解。

4.1 区间的开闭问题

区间的左闭右闭、左闭右开指的是初始待查找区间的范围。

关于左闭右闭、左闭右开，其实在网上都有对应的代码和解法。但是相对来说，左闭右开这种写法在解决问题的过程中，需要考虑的情况更加复杂，所以建议 全部使用「左闭右闭」区间。

4.2 mid 的取值问题

在二分查找的实际问题中，最常见的 mid 取值就是 mid = (left + right) // 2 或者 mid = left + (right - left) // 2。前者是最常见写法，后者是为了防止整型溢出。式子中 // 2 就代表的含义是中间数「向下取整」。当待查找区间中有偶数个元素个数时，则位于最中间的数为 2 个，这时候使用上面式子只能取到中间靠左边那个数，而取不到中间靠右边的那个数。那么，右边的那个数到底能取吗？

其实，右边的数也是可以取的，令 mid = (left + right + 1) // 2，或者 mid = left + (right - left + 1) // 2。这样如果待查找区间的元素为偶数个，就能取到中间靠右边的那个数了，把这个式子代入到 704. 二分查找 中试一试，发现也是能通过题目评测的。

这是因为二分查找的思路是根据每次选择中间位置上的数值来决定下一次在哪个区间查找元素。每一次选择的元素位置可以是中间位置，但并不是一定非得是区间中间位置元素，靠左一些、靠右一些、甚至区间三分之一、五分之一处等等，都是可以的。比如说 mid = left + (right - left + 1) * 1 // 5 也是可以的。

但一般来说，取中间位置元素在平均意义下所达到的效果最好。同时这样写最简单。而对于 mid 值是向下取整还是向上取整，大多数时候是选择不加 1。但有些写法中，是需要考虑加 1 的，这个后面会说这种写法。

4.3 出界条件的判断

我们经常看到二分查找算法的写法中，while 语句出界判断的语句有left <= right 和 left < right 两种写法。那我们究竟应该在什么情况用什么写法呢？

但是如果我们还是想要使用 left < right 的话，怎么办？

可以在返回的时候需要增加一层判断，判断 left 所指向位置是否等于目标元素，如果是的话就返回 left，如果不是的话返回 -1。即：

# ...
    while left < right:
        # ...
    return left if nums[left] == target else -1

此外，用 left < right 的话还有一个好处，就是退出循环的时候 left == right 成立，就不用判断应该返回 left 还是 right 了。

4.4 搜索区间范围的选择

在进行区间范围选择的时候，有时候是 left = mid + 1、right = mid - 1，还有的时候是 left = mid + 1、right = mid，还有的时候是 left = mid、right = mid - 1。那么我们到底应该如何确定搜索区间范围呢？

这是二分查找的一个难点，写错了很容易造成死循环，或者得不到正确结果。

这其实跟二分查找算法的两种不同思路有关。

接下来我们具体讲解下这两种思路。

5. 二分查找两种思路

5.1 思路 1：「直接找」

第 1 种思路比较简单，一旦我们在循环体中找到元素就直接返回结果。其实我们在上边 「3. 简单二分查找 - 704. 二分查找」 中就已经用过了。这里再看一下思路和代码：

思路：

代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        # 在区间 [left, right] 内查找 target
        while left <= right:
            # 取区间中间节点
            mid = left + (right - left) // 2
            # 如果找到目标值，则直接范围中心位置
            if nums[mid] == target:
                return mid
            # 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
            elif nums[mid] < target:
                left = mid + 1
            # 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
            else:
                right = mid - 1
        # 未搜索到元素，返回 -1
        return -1

细节：

5.2 思路 2：「排除法」

第 2 种思路在循环体中排除目标元素一定不存在区间。

思路：

根据第二种排除法的思路，我们可以写出来两种代码。

第一种代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        # 在区间 [left, right] 内查找 target
        while left < right:
            # 取区间中间节点
            mid = left + (right - left) // 2
            # nums[mid] 小于目标值，排除掉不可能区间 [left, mid]，在 [mid + 1, right] 中继续搜索
            if nums[mid] < target:
                left = mid + 1 
            # nums[mid] 大于等于目标值，目标元素可能在 [left, mid] 中，在 [left, mid] 中继续搜索
            else:
                right = mid
        # 判断区间剩余元素是否为目标元素，不是则返回 -1
        return left if nums[left] == target else -1

第二种代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        # 在区间 [left, right] 内查找 target
        while left < right:
            # 取区间中间节点
            mid = left + (right - left + 1) // 2
            # nums[mid] 大于目标值，排除掉不可能区间 [mid, right]，在 [left, mid - 1] 中继续搜索
            if nums[mid] > target:
                right = mid - 1 
            # nums[mid] 小于等于目标值，目标元素可能在 [mid, right] 中，在 [mid, right] 中继续搜索
            else:
                left = mid
        # 判断区间剩余元素是否为目标元素，不是则返回 -1
        return left if nums[left] == target else -1

细节：

5.3 两种思路适用范围

参考资料

上一篇下一篇

猜你喜欢

热点阅读