二分查找习题篇(上)

1.二分查找

题目描述：

给定⼀个 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]之间。

解法一：暴力解法

从前往后枚举每一个元素，将其与目标值进行对比。

时间复杂度最差为O(N)。

解法二：二分查找算法

当数组具有“二段性”时，我们就可以用二分查找算法。

算法思路：

1. 定义 left ， right 指针，分别指向数组的左右区间。

2. 当left<=right时，下列一直循环：

​ 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：

• arr[mid] == target：返回 mid 的值；
• arr[mid] > target：让 right = mid - 1，在 [left, right] 的区间继续查找 ,重复 2 过程；
• arr[mid] < target：让 left = mid + 1, 在 [left, right] 的区间继续查找，重复 2 过程；

3. 当left>right时，说明整个区间都没有这个数，返回 -1 。

细节问题：

1.循环结束的条件

当left>right

2.为什么是正确的？

二分查找是从暴力解法优化而来的

3.时间复杂度

1次——>n/2¹=n/2

2次——>n/2²=n/4

3次——>n/2³=n/8

…次——>…

x次——>n/2^x=1(当left==right，找到要找的元素时)

2^x=n——>x=logN

因此，二分查找的时间复杂度是logN.

代码实现：

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right)//每次查找的元素都是未知的，所以要取等号{int mid=left+(right-left)/2;  //防止溢出if(nums[mid]>target) right=mid-1;else if(nums[mid]<target) left=mid+1;else return mid;}return -1;}
};

朴素二分模版：

​ while(left<=right)//每次查找的元素都是未知的，所以要取等号
​ {
​ int mid=left+(right-left)/2; //防止溢出，替换成left+（right-left+1)也可以，只不过是偶数个元素时，mid有2个中间值，左右均可
​ if(……)

​ right=mid-1;
​ else if(……)

​ left=mid+1;
​ else

​ return ……;
​ }

2.在排序数组中查找元素的第一个和最后一个位置

题目描述：

给你一个按照非递减顺序排列(趋势要么递增要么不变)的整数数组 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⁵
• -10⁹ <= nums[i] <= 10⁹
• nums 是一个非递减数组
• -10⁹ <= target <= 10⁹

解法一：暴力查找

从前往后枚举每一个元素，将其与目标值进行对比，相同时记为begin，继续向后寻找，直到找到该数的末尾位置记为end。返回begin,end即可。

时间复杂度最差为O(N)。

解法二：二分查找

当数组具有“二段性”时，我们就可以用二分查找算法。接下来我们来寻找该数组的“二段性”.

记左边界为Bleft，右边界为Bright.

1.查找区间的左端点

这里，我们把数组的元素分为两部分——小于target的部分[left,Bleft-1] and 大于等于target的部分[Bleft,right]。

• 当mid在[left,Bleft-1]的区间，要找左区间，我们可以直接舍去[left,mid]，更新left=mid+1;
• 当mid在[Bleft,right]的区间，要找左区间，我们可以直接舍去[mid+1,right]，更新right=mid(因为mid可能是最终结果)；
• 之后在[left,right]上继续寻找左边界。

细节处理：

1.循环条件：

left<right；

• left=right时，就是最终结果，无需判断；如果判断，就会死循环。

2.求中点的操作：

• 正确写法：left+(right-left)/2：求的是靠左的位置（向下调整）。

• 找左端点时求中点要向下取整。

  要是向上调整，判断之后，当mid在[Bleft,right]时，要更新right=mid。再进行下一次判断，要是又面对同样的情况，又更新right=mid……又循环往复……

2.查找区间右端点：

这里，我们把数组的元素分为两部分——小于等于target的部分[left,Bright] and 大于target的部分[Bright+1,right]。

• 当mid在[left,Bright]的区间，要找右区间，我们可以直接舍去[left,mid-1]，更新left=mid(因为mid可能是最终结果);
• 当mid在[Bright+1,right]的区间，要找右区间，我们可以直接舍去[mid,right]，更新right=mid-1;
• 之后在[left,right]上继续寻找右边界。

细节处理：

1.循环条件：

left<right

2.求中点的操作：

• 正确写法：left+(right-left+1)/2：求的是靠右的位置（向上调整）;

• 找右端点时求中点要向上取整。

  要是向下调整，判断之后，当mid落在[left,Bright]时，要更新left=mid。再进行下一次判断，要是又面对同样的情况，又要更新left=mid……又循环往复……

代码实现：

class Solution
{
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况if(nums.size() == 0) return {-1, -1};int begin = 0;// 1. 二分左端点int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}// 判断是否有结果if(nums[left] != target) return {-1, -1};else begin = left; // 标记⼀下左端点// 2. 二分右端点left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}return {begin, right};}
};

查找区间左端点的模版：

while(left < right)
{
int mid = left + (right - left) / 2;
if(……) left = mid + 1;
else right = mid;
}

查找区间右端点的模版：

while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(……) left = mid;
else right = mid - 1;
}

总结切记：分类讨论的代码，就题论题即可。

3.搜索插入位置

题目描述：

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

请必须使用时间复杂度为 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. 设插入位置的坐标为x，根据插入位置的特点可以把数组的元素分为两部分——小于target的部分[left , x-1] and 大于等于target的部分[x , right]。

• 当mid在[left, x-1]的区间，我们可以直接舍去[left, mid]，更新left=mid+1;
• 当mid在[x, right]的区间，我们可以直接舍去[mid+1,right]，更新right=mid(因为mid可能是最终结果)；
• 之后在[left,right]上继续查找。

2. 直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果。

代码实现：

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

4.x 的平方根

题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

​ 输入：x = 4
​ 输出：2

示例 2：

​ 输入：x = 8
​ 输出：2

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

解法一：暴力查找

算法思路：

依次枚举 [0, x] 之间的所有数 i ：

• 如果 i * i == x ，直接返回 x ；

• 如果 i * i > x ，说明之前的⼀个数是结果，返回 i - 1 。

由于 i * i 可能超过 int 的最大值，因此使用 long long 类型。

代码实现：

class Solution {
public:int mySqrt(int x) {// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlong long i = 0;for (i = 0; i <= x; i++){// 如果两个数相乘正好等于 x，直接返回 iif (i * i == x) return i;// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数if (i * i > x) return i - 1;}// 为了处理oj题需要控制所有路径都有返回值return -1;}
};

解法二：二分查找

本题数组具有“二段性”时，我们就可以用二分查找算法。

算法思路：

这里，我们把数组的元素分为两部分——平方后小于等于x的部分[1,mid] and 平方后大于x的部分[mid-1, x]。

1. 定义 left ， right 指针，分别指向数组的左右区间。

2. 当left<right时，下列一直循环：

​ 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：

• mid*mid<=x：更新left=mid
• mid*mid>x：更新right=mid-1

代码实现：

class Solution
{
public:int mySqrt(int x) {if(x < 1) return 0; // 处理边界情况int left = 1, right = x;while(left < right){long long mid = left + (right - left + 1) / 2; // 防溢出if(mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};

最后，本篇文章到此结束，感觉不错的友友们可以一键三连支持一下笔者，有任何问题欢迎在评论区留言哦~