LeetCode刷题笔记 二分查找 基础应用

二分查找简介

​ 二分查找也常被称为二分法或者折半查找，它是一种在有序数组中查找某一特定元素的查找算法。这种查找方法将查找的时间复杂度从原本的线性时间提升到了对数时间范围，大大缩短了搜索时间。对于一个长度为 O(n) 的数组，二分查找的时间复杂度为 O(log n)。

​ 举例来说，给定一个排好序的数组 {3,4,5,6,7}，我们希望查找 4 在不在这个数组内。第一次折半时考虑中位数 5，因为 5 大于 4, 所以如果 4 存在于这个数组，那么其必定存在于 5 左边这一半。于是我们的查找区间变成了 {3,4,5}。根据具体情况和您的刷题习惯，这里的 5 可以保留也可以不保留，并不影响时间复杂度的级别。第二次折半时考虑新的中位数 4，正好是我们是需要查找的数字。于是我们发现，对于一个长度为 5 的数组，我们只进行了 2 次查找。如果是遍历数组，最坏的情况则需要查找 5 次。

​ 具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍，第一是尝试熟练使用一种写法，比如左闭右开（满足 C++、Python 等语言的习惯）或左闭右闭（便于处理边界条件），尽量只保持这一种写法；第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。我们给出左闭右开的二分查找基本程序结构如下：

int basicBinarySearch(vector<int> arr, int target){int left = 0;int right = arr.size();while(left < right){int mid = left + (right-left)/2;if(arr[mid] == target){return mid;}else if (arr[mid] > target){right = mid; }else{left = mid + 1;}}return -1;
}

​ 二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题，指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。

​ 二分查找最为基础的应用就是在有序数组中查找某一特定元素，即查找数组中的某个值。

35 搜索插入位置

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

输入一个数组和一个目标值，输出一个整数表示目标值插入的位置

输入: nums = [1,3,5,6], target = 2
输出: 1

解析：

​ 题目要求使用时间复杂度为 O(log n) 的算法。我们可以考虑使用二分查找来寻找合适位置，计算中间位置 mid，有如下三种情况：

nums[mid] == target 那么 mid 的位置就是插入位置nums[mid] > target 那么其插入位置在 mid 的左侧nums[mid] < target 那么其插入位置在 mid 的右侧

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();int pos = -1;while(left<right){int mid = left + (right-left)/2;if(nums[mid] == target){return mid;}else if(nums[mid] > target){right = mid;}else{left = mid + 1;}}return left;}
};

69 Sqrt(x)

给定一个非负整数 x ，计算并返回 x 的 算术平方根 ，由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

输入一个整数，输出一个整数。

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

解析：

​ 我们可以把这道题想象成，给定一个非负整数 a，求 f (x) = x^2 − a = 0 的解。因为我们只考虑 x ≥ 0，所以 f (x) 在定义域上是单调递增的。考虑到 f (0) = −a ≤ 0， f (a) = a^2 − a ≥ 0，我们可以对 [0, a] 区间使用二分法找到 f (x) = 0 的解。

​ 值得注意的是，为了防止除以 0，我们把 a = 0 的情况单独考虑，然后对区间 [1, a] 进行二分查找；同时，我们采用左闭右开的写法所以 a = 1 时会出现结果处理不一致的情况也要单独考虑。

class Solution {
public:int mySqrt(int x) {if(!x) return 0;int left = 1, right = x;if(left==right) return left;while(left<right){int mid = left + (right-left)/2;int sqrt = x/mid;if(mid == sqrt){return mid;}else if(mid > sqrt){right = mid;}else{left = mid+1;}}return left-1;}
};

74 搜索二维矩阵

给定一个 m x n 二维矩阵，已知每行从左到右按升序排列，尝试设计一个快速搜索一个数字是否在矩阵中存在的算法。

输入是一个二维整数矩阵，和一个待搜索整数。输出是一个布尔值，表示这个整数是否存在于矩阵中。

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

解析：

​ 本题使用二分查找有两种思路，一种是先对列二分查找然后对行二分查找，这种两次查找完成搜索；另一种则是将二维数组展平为一个一维数组，然后在该基础上进行二分查找。

​ 这里介绍第二种方法，当然我们不需要真的去做二维数组到一维数组的转化，而是用一维数组的索引去映射二维数组的元素位置。例如，一维数组中索引为 6 的元素映射到 3X4 的二维数组中的位置为matrix[6/4][6%4] 即 matrix[1][2]。又数组整体为递增关系，所以可以方便的采用二分查找搜索元素。当然这种方法中，如果二维矩阵不是对齐的就无法正确应用。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int left = 0, right = m*n;while(left<right){int mid = left + (right-left)/2;if(matrix[mid/n][mid%n] == target){return true;}else if(matrix[mid/n][mid%n] > target){right = mid;}else{left = mid + 1;}}return false;}
};

​ 除了二分查找，对于这种元素呈现从左上角向右下角递增的排列方式，我们可以直接利用其特性进行快速剪枝搜索目标元素。从矩阵右上角开始搜索 target，如果 target 大于当前值就向下移动，当前行被剪枝；如果 target 小于当前值就向左移动，当前列被剪枝。通过这种快速剪枝的策略可以快速完成搜索。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if(matrix.empty() || matrix[0].empty()){return false;} int m = matrix.size(), n = matrix[0].size();int i = 0, j = n-1;while(i<m && j>=0){if(target == matrix[i][j]){return true;}else if(target < matrix[i][j]){--j;}else{++i;}}return false;}
};

540 有序数组中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

输入一个数组，输出一个整型值表示数组中唯一仅出现一次的元素。

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

解析：

​ 借助本题我们可以进一步抽象二分查找的应用场景。一般的二分查找应用场景都是根据目标值来将整个数组划分为两部分，一部分整体大于等于目标值，另一部分整体小于目标值。

​ 我们可以进一步抽象二分法为：将数组整体划分为两个局部连续区间，这两个局部区间具有相对的性质。

​ 在本题中采用二分法，我们可以将两个局部区间分为区间长度为偶数和奇数两部分，而奇数区间内就包含着那个唯一出现一次的元素。

​ 使用二分法解决本题的步骤如下：

计算 mid，并判断当前元素是出现一次还是两次如果仅出现一次即 nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]，直接返回当前元素如果出现两次就要考虑两种情况，即nums[mid] == nums[mid-1] 还是 nums[mid] == nums[mid+1]。如果是前者，判断[0,mid]区间长度是偶数还是奇数，偶数则在 mid 右侧区间找分界点即left = mid + 1，奇数则在 mid 左侧区间找分界点即right = mid - 1；同理，如果是后者判断[0,mid-1]区间长度为奇数还是偶数，并进行相似操作。

class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int left = 0, right = nums.size();while(left<right){int mid = left + (right-left)/2;// 元素出现两次的情况 nums[mid] == nums[mid-1]if(mid > 0 && nums[mid] == nums[mid-1]){// 判断区间长度的奇偶性，与运算，奇数与0001进行与运算结果为1,偶数为0。mid表示的是元素位置if(mid&1){left = mid + 1;}else{right = mid - 1;}// 元素出现两次的情况 nums[mid] == nums[mid+1]}else if(mid < nums.size()-1 && nums[mid] == nums[mid+1]){// 判断区间长度的奇偶性if(mid&1){right = mid;}else{left = mid + 2;}}else{return nums[mid];}}return -1;}
};

​ 当然本题也可以使用异或运算的特性快速解决，与自身进行异或运算结果为0，与0进行异或运算的结果为自身x^x=0, x^0=x。利用这一特性我们将数组元素逐一进行异或运算就可以得到只出现一次的元素了。

class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int ans = 0;for(const auto num:nums){ans ^= num;}return ans;}
};

参考资料

LeetCode 101：和你一起轻松刷题(C++) 第 4 章 居合斩！二分查找

一文带你刷遍二分查找（视频+绘图）