Python - 深夜数据结构与算法之 Binary Search

一.引言

二.二分查找的简介

1.查找条件

2.代码模版

3.查找示例

三.经典算法实战

1.Search-Rotated-List [33]

2.Sqrt-X [69]

3.Search-2D-Matrix [74]

4.Find-Rotated-Min [153]

5.Valid-Perfect-Square [367]

四.总结

一.引言

前面介绍了二叉树和堆，其中涉及到有树和二叉搜索的概念，今天将二者整合介绍下常见的二分查找的问题。

二.二分查找的简介

1.查找条件

单调性 - 如果对应数据不具有单调性性质，则我们只能 o(n) 遍历寻找

上下界 - 存在上下界才能不断缩小范围

索引访问 - 列表可以，单链表的话不支持索引访问不容易二分

2.代码模版

right、left 即为我们的上下界，通过 mid 每次将搜索范围减半，时间复杂度为 log。代码模版中我们默认是升序排列的，如果是降序排序需要修改下elif 和 else 的逻辑，我们主要掌握上面的模版，即 left、rigth 的起始点，如何获取 mid 并判断。

3.查找示例

数组满足有序、有界、索引访问所以可以进行二分查找，不断寻找 mid 缩小 left、right 的范围，就像高数里求数学极限的夹逼准则一样，直到找到 target 或者退出。

三.经典算法实战

1.Search-Rotated-List [33]

搜索旋转排序数组: https://leetcode.cn/problems/search-in-rotated-sorted-array

◆ 题目分析

对一个旋转后的有序数组进行排序，最暴力的方法无非 o(n) 遍历，找到突变的 index，即前后元素不保序，随后将数组恢复为有序再 sort，这个方法是最基础的，不过这里也可以套用二分查找的模版，只不过判断的边界条件会复杂一些，下面尝试下。

◆ 二分查找

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2# 找到了if nums[mid] == target:return midif nums[0] <= nums[mid]: # 左边数组有序 [4,5,6,7,0,1,2]if nums[0] <= target < nums[mid]:right = mid - 1else:left = mid + 1 else: # 右边数组有序 [6,7,0,1,2,4,5]if nums[mid] < target <= nums[len(nums) - 1]:left = mid + 1else:right = mid - 1return -1

这个题要求给出 log(n) 的解法，所以暴力求解是不行的，考虑使用二分查找主要需要明确一个点就是不管数组怎么分，它的左右两边一定是有一边有序的，我们只需要每次二分找有序的那一部分判断 target 在不在即可，不在就去另一边再找。因为 nums[mid] != target，所以两个有序区间都是一开一闭，左边为 '[)' 右边为 '(]'。

2.Sqrt-X [69]

X 的平方根: https://leetcode.cn/problems/sqrtx/description/

◆ 题目分析

此题可以使用二分，我们看下三要素是否满足:

- 单调性 x^2 函数是单调的

- 有界对于 x 的平方根而言，其一定在 0-x 之间，有界

- 索引这个这里不需要了，我们使用 o(1) 的内存就解决了

◆ 二分查找

class Solution(object):def mySqrt(self, x):""":type x: int:rtype: int"""# 左右界left, right = 0, xwhile left <= right:# 取整mid = (left + right) // 2if x >= mid * mid:left = mid + 1else:right = mid - 1return right

如果平方根 re^2 = x，则其整数部分一定满足 x >= int(re)^2。再解释下最后为什么返回 right，这里其实返回 left - 1 也一样，这是因为我们的 x 的平方根一定满足:

re^2 <= x < (re+1)^2

当我们最后一次计算到 mid = (re+1) 时，此时进入 else 逻辑，left = re + 1，right = re，再次计算已经不满足 left <= right 的逻辑了，此时返回 right 或者 left - 1 都是返回 re。

3.Search-2D-Matrix [74]

搜索二维矩阵: https://leetcode.cn/problems/search-a-2d-matrix

◆ 题目分析

给定从左到右递增的二维矩阵，求目标 target 是否存在，这题第一反应我们可以直接将 Matrix Flatten 打平为 1D 的 Array 再执行二分查找即可，还有一种就是分别在列和行上做二分查找，先找到对应行，再找到对应列里是否存在。

◆ 暴力二分查找

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""# 各种边界条件if not matrix:return Falseif target < matrix[0][0] or target > matrix[len(matrix) - 1][len(matrix[0]) - 1]:return Falsenums = [][nums.extend(i) for i in matrix]# 寻找对应行left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return Trueif nums[mid] > target:right = mid - 1else:left = mid + 1return False

先 extend 再二分查找，这样遍历的是 o(mxn)，如果只遍历行与列，则是 o(m + n)。

◆ 精简二分查找

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""# 各种边界条件if not matrix:return Falseif target < matrix[0][0] or target > matrix[len(matrix) - 1][len(matrix[0]) - 1]:return False# 寻找对应行col_nums = [row[0] for row in matrix]left, right = 0, len(col_nums) - 1while left <= right:mid = (left + right) // 2if col_nums[mid] == target:return Trueif col_nums[mid] > target:right = mid - 1else:left = mid + 1# 在对应行操作row_nums = matrix[right]left, right = 0, len(row_nums) - 1while left <= right:mid = (left + right) // 2if row_nums[mid] == target:return Trueif row_nums[mid] > target:right = mid - 1else:left = mid + 1return False

先找 col_nums 找到 target 应该在哪一行，再找 target 在不在 row_nums 里。

4.Find-Rotated-Min [153]

旋转排序最小值: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array

◆ 题目分析

二分查找的本质其实是通过条件缩小每次的检查范围，本题的思路直接想比较麻烦，在记事本上写一下会方便很多，这里我们二分的条件就是找小的在哪，无非左边或右边，所以我们直接列举全部情况即可。

◆ 二分查找

class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""# 完全有序if nums[0] <= nums[-1]:return nums[0]left, right = 0, len(nums) - 1# 找哪边小，去小的那边接着找while left <= right:if nums[left] == nums[right]:return nums[left]mid = (left + right) // 2# [2, 3, 4, 5, 1] 中间比左边大 -> 右边if nums[mid] >= nums[0]:left = mid + 1# [5, 1, 2, 3, 4] 中间比左边小 -> 左边else:right = midreturn nums[left]

nums[0] <= nums[-1] 完全有序，直接出第一个最小的

nums[mid] >= nums[0] 左边有序，最小值在右边 left = mid + 1

nums[mid] < nums[0] 最小值在左边，结合在中间的特殊情况 right = mid

5.Valid-Perfect-Square [367]

有效的完全平方数: https://leetcode-cn.com/problems/valid-perfect-square/

◆ 题目分析

找平方的题目，起始就是找到 re ^^ 2 <= num < (re+1) ^^ 2，此时 left = re+1，right = re，因为我们判断是否是完全平方，所以判断 re ^^ 2 == num 即可。

◆ 二分查找

class Solution(object):def isPerfectSquare(self, num):""":type num: int:rtype: bool"""left, right = 0, numwhile left <= right:mid = (left + right) // 2if num >= mid * mid:left = mid + 1else:right = mid - 1return right ** 2 == num

直接看是否是 int(re) 的平方即可。