Leetcode二分搜索法浅析

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

1.1什么是二分搜索法？

我们来看AI给出的回答：

二分搜索法，又称折半查找算法，是一种在有序列表（如数组）中高效查找特定元素的搜索算法。该算法利用了列表元素已排序的特性，通过反复将待搜索区间分成两半来缩小查找范围，具体步骤如下：

1. 初始化: 确定搜索区间，通常开始时是整个列表，设两个指针分别指向列表的起始位置（low）和结束位置（high）。

2. 计算中间位置: 计算当前搜索区间的中间索引 mid = (low + high) / 2，并获取该位置的元素值。

3. 比较与决策:

   • 如果中间元素正好是要查找的目标，则搜索结束，返回该元素的位置。
   • 如果目标值小于中间元素，则在左半区间（low 到 mid-1）继续搜索，更新 high = mid - 1。
   • 如果目标值大于中间元素，则在右半区间（mid+1 到 high）继续搜索，更新 low = mid + 1。

4. 重复步骤2和3，直到找到目标值或搜索区间为空（即 low > high），此时表明目标值不在列表中。

二分搜索法的时间复杂度为 O(log n)，其中 n 是列表中元素的数量。这意味着对于大规模数据集合，二分搜索远比顺序搜索（时间复杂度为 O(n)）高效。然而，为了应用二分搜索，列表必须事先排序，且通常适用于静态数据或不频繁插入删除操作的数据结构。

可以看出二分搜索法顾名思义就是不断来缩小我们的搜索区间，来查找特定元素的一种高效算法，而在使用二分搜索法时，关键的地方就在于如何确定我们的区间边界。

1.2解法思路

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

开始我们可以给定一个左闭右闭的区间，是左区间left = 0，右区间right = nums.size -1，此时判断边界时就需要考虑：左区间和右区间的关系时小于等于还是小于？

开始我们的思路时给定一个左闭右闭的区间，也就是说左区间的值可以等于右区间，所以在第一个边界判断时，我们的左区间是可以等于右区间的。

当我们对目标值进行判断后，我们的左右区间又该如何判断呢？

第一种情况：当我们所要查找的目标值小于区间中值时，我们需要考虑的是，此时的右区间right是等于madile还是等于madile-1，回到判断条件中nums[madile] > target，这表示我们区间的中值已经大于我们的目标值了，所以我们下一次的判断时，已经不需要考虑madile，所以此时的右区间应该是madile-1。

同样的道理当区间中值小于目标值时，我们要更新左区间的值，此时左区间的值为madile+1。

1.3扩展

题目原文：

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

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

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

这道题使用二分法的思路如下：

要使用二分法找到非负整数 x 的算术平方根的整数部分，你可以遵循以下步骤：

1. 初始化两个指针，left 和 right。因为我们要找的是非负整数的平方根，所以 left 初始化为 0，而 right 初始化为 x。如果 x 是 0，则直接返回 0。

2. 进入一个循环，只要 left 小于等于 right，就继续循环。

3. 在每次循环中，计算 mid，它是 left 和 right 的中间值（向下取整），然后检查 mid * mid 是否等于 x。如果是，那么 mid 就是我们要找的平方根，直接返回它。

4. 如果 mid * mid 大于 x，说明我们超出了目标平方根，因此需要将 right 更新为 mid - 1。

5. 如果 mid * mid 小于 x，说明目标平方根还在 mid 的右侧（包括 mid），因此需要将 left 更新为 mid + 1。

6. 循环结束后，left 会指向我们找到的整数平方根（因为循环条件是 left <= right，当循环停止时，实际上 left 可能已经超过了正确的答案，但由于我们是向下取整寻找平方根，最终正确的整数平方根是 left - 1，除非 x 是完全平方数）。

题解：

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