Leetcode二分搜索法浅析
文章目录
- 1.二分搜索法
- 1.1什么是二分搜索法？
- 1.2解法思路
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。
