【算法专项二】二分查找法

野性酷女 2023-01-20 12:56 19阅读 0赞

# 简介 #

二分查找法，是两大基础算法类别中最典型的一种（排序与搜索）。简单来说，二分搜索通过不断划分取中间点划分区间，以此在极大程度上减少查找的次数。

不过二分查找的前提，是整个数组是**有序**的，并且**数组无重复元素**。  
有序很好理解，对于无重复元素的条件而言，如果一旦有重复元素，使用二分查找法法返回的元素下标就可能不是唯一的。

因此，一旦某个问题满足上述两个条件，就可以考虑问题是否可以使用二分查找法。

对于二分查找的算法中，是存在所谓的“模板”的，但是这里根据`left <= right`和`left < right`的不同，代码的实现方法和逻辑也有很大差别。

**算法原理简介**

上述两种循环判断条件中，本质上是对**二分子区间的开闭选择**：

*  `left <= right`，对应 **\[left, right\]**
 *  `left < right`, 对应 **\[left, right)**

**左闭右闭**

虽然从直觉上来说，第一种可能更直观，因为每次去更新left和right时，都是符合直觉的：

def find_target(nums: list, target: int):
    	left = 0
    	right = len(nums) - 1		# 由于是左闭右闭的区间，因此这里需要取到最右侧能访问的元素
    	while left <= right:
    		mid = left + (right - left) // 2	# 防止大数溢出的写法，其实Python没必要这样处理
    		if nums[mid] == target:
    			return mid
    		elif nums[mid] > target:	# 说明target在左侧区间，即[left, mid - 1]
    			right = mid - 1
    		elif nums[mid] < target:	# 说明target在右侧区间，即[mid + 1, right]
    			left = mid + 1
    	return -1		# 说明没有找到

这种区间划分方法虽然直观，但是存在一个问题：

*  如果因为没找到对应的target而终止搜索，最后left和right的值是不同的。

简单来说，**当搜索区间为空时，终止搜索**。根据`while left <= right`，可知终止条件为**left == right + 1**，如果写成区间的形式就是 **\[right, right+1\]**，或者\[3, 2\]。

这就造成一个问题——当我们需要找到区间为空时的边界值时，就会有left和right，其中只有一个正确答案，这就有可能出错。

**左闭右开**

因此，对于第二种方法而言，查询的区间为 **\[left, right)**，因此，在代码实现上：

def find_target(nums: list, target: int):
    	left = 0
    	right = len(nums) 		# 由于是左闭右开的区间，因此right需要取到最右的开区间位置
    	while left < right:
    		mid = left + (right - left) // 2
    		if nums[mid] == target:
    			return mid
    		elif nums[mid] > target:	# 说明target在左侧区间，即[left, mid)
    			right = mid
    		elif nums[mid] < target:	# 说明target在右侧区间，即[mid + 1, right)
    			left = mid + 1
    	return -1

这里，使用左闭右开区间的好处就体现出来了——当未能找到结果而导致查询区间为空时，\[left, right)此时是相等的，也就是\[left, left) 或\[right, right)，因此不管是nums\[left\]还是nums\[right\]，其结果都是一致的。

针对这种方法，引用知乎上的一个回答：

首先，为何要将区间写成左闭右开呢？其实，我们所使用的区间，一直都是左闭右开的。

比方说，当我们遍历长度为n的数据时，实际上是：

for i in range(n):
    	# 等价于range(0, n)或者range(0, n, 1)
    	# i is in range[0, 0)
    	# do something

其次，在选择中间点时，这个中间点其实是并不唯一的：

*  上位中位数：upperMid = first + length / 2
 *  下位中位数：lowerMid = first + (length - 1) / 2

只有当length为偶数时才会不同，简单通过\[0,3)和\[0,4)就可以很简单看出了。

对于搜索算法而言：

def lower_bound(array, first, last, value):
    	while first < last:
    		mid = first + (last - first) // 2 # 防止溢出
    		if array[mid] < value:
    			first = mid + 1
    		else:
    			last = mid
    	return first # last也可以，因为此时是重合的

**while loop的循环不变量**

首先需要理解while循环里的**loop invariants (循环不变量)——也就是代码跑到while里面时一定成立的条件**：

*  搜索范围\[first, last)不为空，即first < last ；
 *  搜索范围\[first, last)左侧，即\[first0, first)内所有的元素，都小于value，其中first0是first的初始值；
 *  搜索范围\[first, last)右侧，即\[last, last0)内所有元素，都大于等于value，即last0是last的初始值。

比方说，待搜索的数组array = \[-1, 0, 0, 3, 3, 3, 7, 8, 9\]：

![当算法运行时，初始状态，搜索区间两侧均为空][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70]

在最开始中的状态中，我们可以看到两侧的搜索区间（青色域紫色）均为空。

上图中，`array[mid] >= 3`，说明mid是属于紫色的。

因此，在已知的信息中，需要最大程度地合理扩张紫色区间、缩小黄色区间，此时的操作应该为：

*  将last放在mid的位置，即`last = mid`：

![紫色区间最大限度的向左扩张][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 1]

如上图所示，新的mid满足`array[mid] < 3`，说明此时mid是属于青色的。

因此，在已知信息下，需要最大限度地合理扩张青色区间，缩小黄色区间，因此此时的操作应该是：

*  `first = mid + 1`

![此时搜索空间长度为1，只剩下最后一步，或者是first，或者是last][1_first_last]

此时虽然搜索区间缩小到1了，但是**并不可以直接返回first**，因为此时虽然我们检查了红圈左边和右边，但是却并没有检查红圈本身：

*  如果是红圈是2，那么就需要返回`last`才行。

这里，之所以需要更新`first`或`last`是需要**最大限度地缩小区间**——`first`更新为`mid+1`而非mid、`last`更新为`mid`而非`mid+1`，主要是为了考虑上图中区间长度为1的情况：此时mid是first，mid+1是last，如果选择较弱的更新，就会发现并没有更新、从而导致死循环。

因此，还需要最后一步：上图中`array[mid] >= 3`，`mid`属于紫色，因此需要`last`左移一位使得`last = mid`：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 2]

可以看到，此时`[first, last)`已经为空，青色区间与紫色区间都得到最大限度的扩张。  
因此，根据紫色区间的定义，其中任意元素均≥3，因此，第一个元素的位置——last就是我们所找到的答案。

若没有满足`x >= 3`的元素，那么此时紫色空间就空的，停留在初始状态`[last0, last0)`的状态，因此最后返回的也是last0，即初始范围之外的第一个元素，表示“不存在”。

值得注意的是，找到元素之后，`first`和`last`是重合，因此就不需要纠结到底哪一个是正确的了。

[LeetCode二分查找问题专区][LeetCode]

# 涉及题目 #

## 简单难度 ##

### 35. 搜索插入位置 ###

**题目地址**  
[35. 搜索插入位置][35.]

**题目描述**  
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

> 输入: \[1,3,5,6\], 5  
> 输出: 2

示例 2:

> 输入: \[1,3,5,6\], 2  
> 输出: 1

示例 3:

> 输入: \[1,3,5,6\], 7  
> 输出: 4

示例 4:

> 输入: \[1,3,5,6\], 0  
> 输出: 0

**题目思路**

对于这道题，是一道较为典型的二分查找类问题。

在这道题目中，需要在**无重复元素的升序数组中**，找到对应值元素的下标；同时没有找到，并非返回-1这种值，而是应该返回本应该插入的位置坐标。

这要就要求在**最终查找区间为跳出循环条件**时，`low`或`high`能表示这种对应的下标。

假如说我们使用上述所说的左闭右闭的区间形式，如果没有找到对应的元素，最终终止循环时，**low和high的值是不同的**，这时我们就必须对题目进行分析，知道应该返回的是`low`而非`high`。

而假如我们使用的是第二种左闭右开的查找区间形式，最终终止循环时可知**low和high的值都是相同的**。从而就不必纠结到底应该是`low`或者`high`，只需从题目需求入手分析，可知最后应该返回`low`或者`high`都是可以的。

根据上面的分析，最后停止查找时，右区间内的元素都是大于等于target的，因此，此时右区间的开始元素就是我们所需要查找的最终位置，因此最后返回high、或者low都是可以的。

**题目解法**

class Solution:
        def searchInsert(self, nums: List[int], target: int) -> int:
            low, high = 0, len(nums)
            while low < high:
                mid = low + (high - low) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    high = mid
                elif nums[mid] < target:
                    low = mid + 1
            return low

### 69. x 的平方根 ###

## 中等难度 ##

**题目地址**  
[69. x 的平方根][69. x]

# 参考文章 #

> [左闭右开的二分查找][Link 1]  
> [二分查找有几种写法？它们的区别是什么？][Link 2]  
> [二分查找（面试必备）-segmentfault][-segmentfault]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70]: /images/20221021/ad8aea9ebaea49aebad5ccd92612e0bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 1]: /images/20221021/daa927f3f093493685eee89262f096e9.png
[1_first_last]: /images/20221021/c0ca338d863343079a30a94d031ffae4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 2]: /images/20221021/25edd04336ee41b591288937bfde3b7c.png
[LeetCode]: https://leetcode-cn.com/tag/binary-search/problemset/
[35.]: https://leetcode-cn.com/problems/search-insert-position/
[69. x]: https://leetcode-cn.com/problems/sqrtx/
[Link 1]: https://www.zhihu.com/question/36132386/answer/530313852
[Link 2]: https://www.zhihu.com/question/36132386
[-segmentfault]: https://segmentfault.com/a/1190000008699980