【算法与数据结构】二分查找思想
#1024程序员节｜征文#
正文：
二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止，其实有时候数据没有序也能用二分查找思想解题，遇到具体的题我们具体分析。
我们要想搞清楚二分查找的思想是什么就需要结合具体的题目进行理解，单单靠定义是不行的，下面让我们进入刷题的节奏吧！
一、二分查找
704. 二分查找 - 力扣（LeetCode）
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。
示例 1:输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
这道题用暴力解法是很好写的，只需从前向后遍历数组，若找到，返回下标，否则返回-1。它的时间复杂度为O(N)。
这道题的题目就是二分查找，我们以这个题为代表引出二分查找的思想。
首先这道题目中的数组是升序的，那么给你一个target目标值，要查找target对应的下标。
我们可以先拿到数组中间的数(nums[mid])，让这个数与target作比较：
1、如果相等，就直接返回它的下标(mid)即可。
2、如果nums[mid]大于target，因为是升序，那么后面的值必定大于target，所以只需在[0,mid-1]这个区间找即可(这样数据的范围就减少一半了)。
3、如果nums[mid]小于target，因为是升序，那么前面的值必定小于target，所以只需在[mid+1,n)这个区间找即可(n为元素个数,这样数据的范围也减少一半)。
如果数据量是100w，比较一次，如果运气好就直接找到，如果运气不好，我比较一次就可以减少50w的数据量，可想而知这个算法如果适合使用，那是非常厉害的。
可能会有人问，可以从1/3的位置或1/4的位置处找一个数进行比较可以吗？
答案是可以的，但是这可能不会太"稳定"，以1/3位置为例，运气好可能一次过滤掉大部分数据(3/4)，运气不好可能就只过滤掉1/4的数据。
经过大量研究，认为还是取中间的数更优。
回到这题，代码实现：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0,right=nums.size()-1;
while(left <= right) //这里不是"<"而是"<="，因为left==right时对应的值可能就是目标值
{
int mid = (right-left)/2 + left; //中间位置下标
if(nums[mid] > target)
right = mid-1; //只需更新right
else if(nums[mid] < target)
left = mid+1; //只需更新left
else
return mid;
}
return -1; //没有找到的情况
}
};这道题的代码实现非常简单，但有一个点需要说明一下，就是求中间位置的下标。
一些同学可能会这样写：
int mid = (left + right) / 2;这样写会面临一个问题，当left和right数极大时，它们两个相加可能会超出int最大值，这样计算出的mid就不正确了，我们改写为上面的形式就不会出现"越界"的情景。
还需注意一个点：
对于本题，这两种写法写任意一个都可以。
二分查找的时间复杂度分析：
时间复杂度为logN的算法可比时间复杂度为N的厉害太多了。
1024个数据，时间复杂度为N的算法最多需要找1024次，时间复杂度为logN的算法最多只需要找10次。
1024*1024个数据(大约100万)，时间复杂度为N的算法最多需要找100w次，时间复杂度为logN的算法最多只需要找20次。
二、在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]示例 3：
输入：nums = [], target = 0 输出：[-1,-1]提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums是一个非递减数组-10^9 <= target <= 10^9
这道题的暴力解法是很好想出来的，遍历数组，首次遇到target记录它的下标，然后接着遍历记录最后一个值为target的下标，最后返回即可。
暴力解法代码实现：
//暴力解法：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size();
vector<int> ret;
for(int i=0;i<n;i++)
{
if(nums[i]==target)
ret.push_back(i);
}
if(ret.empty())
return {-1,-1};
return {ret[0],ret[ret.size()-1]};
}
};这道题可以直接用二分查找吗？
这道题可以用二分查找思想，但是不能直接套用第一题的模板样式，分析：
这道题为什么可以用二分思想呢？那么如何使用二分查找思想呢？
分析(以示例1为例)：
别的一些细节，请大家在代码实现中仔细品味。
代码实现：
//二分思想
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty())
return {-1,-1};
vector<int> ret;
//1、二分左端点
int left = 0,right=nums.size()-1;
while(left < right)
{
int mid = (right-left)/2 + left;
if(nums[mid] < target)
left = mid+1;
else
right = mid;
}
if(nums[left] != target)
return{-1,-1};
ret.push_back(left);
//2、二分右端点
left = 0,right = nums.size()-1;
while(left<right)
{
int mid = (right-left+1)/2+left;
if(nums[mid] > target)
right = mid-1;
else
left = mid;
}
ret.push_back(right);
return ret;
}
};三、搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4提示:
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4
这道题其实和第二题本质上是一样的，只是换一种形式和说法，就是第二题中求左端点的下标的问题。因为nums是无重复元素的升序排列数组，可以实现"分段"，所以就是第二题的变形，我们直接上代码：
//二分思想
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left < right)
{
int mid = (right-left)/2+left;
if(nums[mid] < target)
left=mid+1;
else
right=mid;
}
if(nums[right] < target) //处理特殊情况，应对示例3出现的情况
return right+1;
return right;
}
};它的复杂度也符合题目中的O(logN)。
四、x 的平方根
69. x 的平方根 - 力扣（LeetCode）
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <= 2^31 - 1
这道题的暴力解法就是从1开始遍历看看哪个数的平方等于x，就返回，如果大于x，就返回一个数。
经过前面几个题的解题过程，这道题不就是第二道题中求右端点位置下标的变形嘛。想象数组中的元素从1到x，简直不要太一样了，直接上代码：
class Solution {
public:
int mySqrt(int x) {
int left = 1,right = x;
while(left<right)
{
long long mid = (right-left+1)/2+left;
if(mid*mid > x) //为了防止溢出，mid的类型用long long
right= mid-1;
else
left = mid;
}
return right;
}
};
五、山脉数组的峰顶索引
852. 山脉数组的峰顶索引 - 力扣（LeetCode）
给定一个长度为
n的整数 山脉 数组arr，其中的值递增到一个 峰值元素 然后递减。返回峰值元素的下标。
你必须设计并实现时间复杂度为
O(log(n))的解决方案。示例 1：
输入：arr = [0,1,0] 输出：1示例 2：
输入：arr = [0,2,1,0] 输出：1示例 3：
输入：arr = [0,10,5,2] 输出：1提示：
3 <= arr.length <= 10^50 <= arr[i] <= 10^6- 题目数据 保证
arr是一个山脉数组
这道题用暴力解法就是从头遍历数组，如果当前数比后一个大，那么这个数就是峰值，返回其下标即可。
暴力解法代码：
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
// 遍历数组内每⼀个元素，直到找到峰顶
for (int i = 1; i < n - 1; i++)
// 峰顶满⾜的条件
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
return i;
// 为了处理 oj 需要控制所有路径都有返回值
return -1;
}
};这道题中的数组是可以分段的，分析如下：
这道题的本质就是第二道题求左端点问题。
代码如下:
//二分思想
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n=arr.size();
int left = 1,right=n-2; //峰顶不可能是第一个元素和最后一个元素
while(left < right)
{
int mid = (right-left)/2+left;
if(arr[mid] < arr[mid+1])
left = mid+1;
else
right = mid;
}
return left;
}
};时间复杂度满足O(logN)。
六、 寻找峰值
162. 寻找峰值 - 力扣（LeetCode）
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设
nums[-1] = nums[n] = -∞。你必须实现时间复杂度为
O(log n)的算法来解决此问题。示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。提示：
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
经过题目描述，这道题会有以下几种情况：
我们可以将以上3中情况抽象为2种：
代码实现：
//二分思想
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
int left=0,right=n-1;
while(left<right)
{
int mid = (right-left)/2+left;
if(nums[mid]<nums[mid+1])
left = mid + 1;
else
right = mid;
}
return left;
}
};时间复杂度满足O(logN)。
五、六两题种数据并没有序，我们也能用二分查找思想解题，所以我们不要将二分思想局限到只能在有序数组中去运用。
七、寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
这道题的暴力解法是遍历数组，如果当前值比下一个值大，就返回下一个元素；如果遍历完没有找到就返回第一个元素。暴力解法的时间复杂度是O(N)。
这道题很明显有分段情况，我们可以考虑用二分思想：
这道题本质上就是第二题中的求左端点问题。
代码实现：
//二分思想(以D为基准)
class Solution {
public:
int findMin(vector<int>& nums) {
int n=nums.size();
int base = nums[n-1]; //以最后一个元素为基准值
int left=0,right=n-1;
while(left<right)
{
int mid = (right-left)/2+left;
if(nums[mid] > base)
left=mid+1;
else
right = mid;
}
return nums[left];
}
};以D为基准值，这段代码可以应对旋转后保持不变的情况。
我们也可以以A为基准值：
//二分思想(以A为基准)
class Solution {
public:
int findMin(vector<int>& nums) {
int n=nums.size();
int base = nums[0]; //以第一个元素为基准值
int left=0,right=n-1;
while(left<right)
{
int mid = (right-left)/2+left;
if(nums[mid] < base)
right=mid;
else
left = mid+1;
}
if(n == 1 || nums[left]>nums[left-1]) //处理旋转后保持不变的情况以及数组只有一个元素的情况
return nums[0];
return nums[left];
}
};时间复杂度满足O(logN)。
八、点名
LCR 173. 点名 - 力扣（LeetCode）
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组
records。假定仅有一位同学缺席，请返回他的学号。示例 1:
输入: records = [0,1,2,3,5] 输出: 4示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7提示：
1 <= records.length <= 10000
这个题的解题方法有很多：
1、异或法
开一个n个元素的数组，记录从0~n-1的所有值。新数组中所有数和records中所有元素异或，异或是"同0不1"，所有异或后，剩下的那个值就是缺席同学的学号。
代码实现：
//异或法
class Solution {
public:
int takeAttendance(vector<int>& records) {
int ret=0; //记录最终结果
int n = records.size()+1;
vector<int> tmp(n); //新开的数组
for(int i=0;i<n;i++)
tmp.push_back(i);
for(auto e: records)
ret^=e;
for(auto e:tmp)
ret^=e;
return ret;
}
};代码还可以更简洁：
//异或法
class Solution {
public:
int takeAttendance(vector<int>& records) {
int ret=0;
int n = records.size();
for(int i=0;i <= n;i++)
{
if(i < n)
ret = ret ^ records[i] ^ i;
else
ret^=i;
}
return ret;
}
};2、 数学法(高斯求和)
利用高斯求和公式求出0~n-1所有数的和然后减去records中所有元素相加的和，结果就是缺席同学的学号。
代码实现：
// 数学法(高斯求和)
class Solution {
public:
int takeAttendance(vector<int>& records) {
int n = records.size() + 1;
int sum1 = ((0 + (n - 1)) * n) / 2; // 0~n-1的和
int sum2 = 0; // recoeds中所有元素的和
for (auto e : records)
sum2 += e;
return sum1 - sum2;
}
};3、哈希思想
记录records中每个元素出现的次数，然后从0开始遍历，如果次数是0，就返回对应的数字。
代码实现：
//哈希映射
class Solution {
public:
int takeAttendance(vector<int>& records) {
int n = records.size()+1;
unordered_map<int,int> hash;
for(auto e:records)
hash[e]++; //记录每个元素出现的次数
for(int i=0;i<n;i++)
if(hash[i]==0)
return i; //缺失的数字
return -1;
}
};4、遍历法
//直接遍历法
class Solution {
public:
int takeAttendance(vector<int>& records) {
int n = records.size();
int i=0;
for(i=0;i<n;i++)
{
if(records[i] != i)
return i;
}
if(i == n) //处理数组是[0,1,2]类似这种的情况
return i;
return -1;
}
};5、二分查找法
通过前面七道题的熏陶，这道题大家自己想如何用二分查找。
我在这里给出代码，大家可以参考一下：
//二分查找
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left=0,right=records.size()-1;
while(left < right)
{
int mid = (right-left)/2+left;
if(records[mid] == mid)
left=mid+1;
else
right=mid;
}
if(records[right] == right) //处理类似[0,1,2]这种数组的情况
return right+1;
return right;
}
};