01. 二分查找知识（一）

1. 二分查找算法介绍

1.1 二分查找算法简介

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

二分查找的基本算法思想为：通过确定目标元素所在的区间范围，反复将查找范围减半，直到找到元素或找不到该元素为止。

1.2 二分查找算法步骤

以下是二分查找算法的基本步骤：

初始化：首先，确定要查找的有序数据集合。可以是一个数组或列表，确保其中的元素按照升序或者降序排列。
确定查找范围：将整个有序数组集合的查找范围确定为整个数组范围区间，即左边界 $l e f t$ 和右边界 $r i g h t$ 。
计算中间元素：根据 $m i d = ⌊ (l e f t + r i g h t) / 2 ⌋$ 计算出中间元素下标位置 $m i d$ 。
比较中间元素：将目标元素 $t a r g e t$ 与中间元素 $n u m s [m i d]$ 进行比较：
1. 如果 $t a r g e t == n u m s [m i d]$ ，说明找到 $t a r g e t$ ，因此返回中间元素的下标位置 $m i d$ 。
2. 如果 $t a r g e t < n u m s [m i d]$ ，说明目标元素在左半部分（ $[l e f t, m i d - 1]$ ），更新右边界为中间元素的前一个位置，即 $r i g h t = m i d - 1$ 。
3. 如果 $t a r g e t > n u m s [m i d]$ ，说明目标元素在右半部分（ $[m i d + 1, r i g h t]$ ），更新左边界为中间元素的后一个位置，即 $l e f t = m i d + 1$ 。
重复步骤 $3 \sim 4$ ，直到找到目标元素时返回中间元素下标位置，或者查找范围缩小为空（左边界大于右边界），表示目标元素不存在，此时返回 $- 1$ 。

举个例子来说，以在有序数组 $[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ 中查找目标元素 $6$ 来说，使用二分查找算法的步骤如下：

确定查找范围：初始时左边界 $l e f t = 0$ （数组的起始位置）， $r i g h t = 10$ （数组的末尾位置）。此时查找范围为 $[0, 10]$ 。
计算中间元素：中间元素下标位置 $m i d = (0 + 10) \div 2 = 5$ ，对应元素为 $n u m s [5] == 5$ 。
比较中间元素：因为 $6 > n u m s [5]$ ，所以目标元素可能在右半部分，更新左边界为中间元素的后一个位置，即 $l e f t = 6$ 。此时查找范围为 $[6, 10]$ 。
计算中间元素：中间元素下标位置 $m i d = (6 + 10) \div 2 = 8$ ，对应元素为 $n u m s [8] == 8$ 。
比较中间元素：因为 $6 < n u m s [8]$ ，所以目标元素可能在左半部分，更新右边界为中间元素的前一个位置，即 $r i g h t = 7$ 。此时查找范围为 $[6, 7]$ 。
计算中间元素：中间元素下标位置 $m i d = (6 + 7) \div 2 = 6$ （向下取整），对应元素为 $n u m s [6] == 6$ 。
比较中间元素：因为 $6 == n u m s [6]$ ，正好是我们正在查找的目标元素，此时返回中间元素的下标位置，算法结束。

于是我们发现，对于一个长度为 $10$ 的有序数组，我们只进行了 $3$ 次查找就找到了目标元素。而如果是按照顺序依次遍历数组，则在最坏情况下，我们可能需要查找 $10$ 次才能找到目标元素。

::: tabs#BinarySearch

@tab <1>

@tab <2>

@tab <3>

@tab <4>

@tab <5>

@tab <6>

@tab <7>

@tab <8>

:::

1.2 二分查找算法思想

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

这里的 「减」 是减少问题规模的意思，「治」 是解决问题的意思。「减」 和 「治」 结合起来的意思就是 「排除法解决问题」。即：每一次查找，排除掉一定不存在目标元素的区间，在剩下可能存在目标元素的区间中继续查找。

每一次通过一些条件判断，将待搜索的区间逐渐缩小，以达到「减少问题规模」的目的。而于问题的规模是有限的，经过有限次的查找，最终会查找到目标元素或者查找失败。

2. 简单二分查找

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

题目链接：704. 二分查找

2.1 题目大意

描述：给定一个升序的数组 $n u m s$ ，和一个目标值 $t a r g e t$ 。

要求：返回 $t a r g e t$ 在数组中的位置，如果找不到，则返回 $- 1$ 。

说明：

你可以假设 $n u m s$ 中的所有元素是不重复的。
$n$ 将在 $[1, 10000]$ 之间。
$n u m s$ 的每个元素都将在 $[- 9999, 9999]$ 之间。

示例：

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

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

2.2 解题思路

思路 1：二分查找

设定左右边界为数组两端，即 $l e f t = 0$ ， $r i g h t = l e n (n u m s) - 1$ ，代表待查找区间为 $[l e f t, r i g h t]$ （左闭右闭区间）。
取两个节点中心位置 $m i d$ ，先比较中心位置值 $n u m s [m i d]$ 与目标值 $t a r g e t$ 的大小。
1. 如果 $t a r g e t == n u m s [m i d]$ ，则返回中心位置。
2. 如果 $t a r g e t > n u m s [m i d]$ ，则将左节点设置为 $m i d + 1$ ，然后继续在右区间 $[m i d + 1, r i g h t]$ 搜索。
3. 如果 $t a r g e t < n u m s [m i d]$ ，则将右节点设置为 $m i d - 1$ ，然后继续在左区间 $[l e f t, m i d - 1]$ 搜索。
如果左边界大于右边界，查找范围缩小为空，说明目标元素不存在，此时返回 $- 1$ 。

思路 1：代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, 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

思路 1：复杂度分析

时间复杂度： $O (\log n)$ 。
空间复杂度： $O (1)$ 。

来源：https://github.com/itcharge/LeetCode-Py