文章目录
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给出的回答：
二分搜索法，又称折半查找算法，是一种在有序列表（如数组）中高效查找特定元素的搜索算法。该算法利用了列表元素已排序的特性，通过反复将待搜索区间分成两半来缩小查找范围，具体步骤如下：
初始化: 确定搜索区间，通常开始时是整个列表，设两个指针分别指向列表的起始位置（low）和结束位置（high）。
计算中间位置: 计算当前搜索区间的中间索引 mid = (low + high) / 2，并获取该位置的元素值。
比较与决策:
- 如果中间元素正好是要查找的目标，则搜索结束，返回该元素的位置。
- 如果目标值小于中间元素，则在左半区间（low 到 mid-1）继续搜索，更新 high = mid - 1。
- 如果目标值大于中间元素，则在右半区间（mid+1 到 high）继续搜索，更新 low = mid + 1。
重复步骤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 的算术平方根的整数部分，你可以遵循以下步骤：
初始化两个指针，
left和right。因为我们要找的是非负整数的平方根，所以left初始化为 0，而right初始化为x。如果x是 0，则直接返回 0。进入一个循环，只要
left小于等于right，就继续循环。在每次循环中，计算
mid，它是left和right的中间值（向下取整），然后检查mid * mid是否等于x。如果是，那么mid就是我们要找的平方根，直接返回它。如果
mid * mid大于x，说明我们超出了目标平方根，因此需要将right更新为mid - 1。如果
mid * mid小于x，说明目标平方根还在mid的右侧（包括mid），因此需要将left更新为mid + 1。循环结束后，
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;
}
};
