【刷题日记】8.二分查找

news/2024/4/30 10:50:14/文章来源:https://blog.csdn.net/m0_62179366/article/details/126974148

题目链接：704. 二分查找 - 力扣（LeetCode）

一、题目介绍

二、思路

左闭右闭区间写法

三、代码

总结

题目链接：704. 二分查找 - 力扣（LeetCode）

一、题目介绍

这道题就是基本的二分查找，找到返回元素下标，没有找到返回-1

很多人都会对这道题不屑一顾，但是小小的二分也有很多的讲究

二分查找的时间复杂度为O(logN)

不过要记住二分查找的条件是数组已经排好序了，并且数组中元素没有重复

二、思路

二分查找主要分为两种，一种是左闭右闭区间[left, right]，另一种是左闭右开区间[left, right)

这两种不同的区间划分方式，决定了循环的条件

我们在写二分查找时很多人都会分不清到底是left < right还是left <= right？

小于还是小于等于，取决于区间的划分

左闭右闭区间写法

左闭右闭区间所对应的循环条件是left <= right

很多人会问为什么？

我们可以画图来观察

我们可以观察到如果要遍历完整个数组，在左闭右闭的情况下需要我们让left <= right

接下来我们就要计算下标的中间值mid

mid = (left + right) / 2；

这种方式看似没有问题实际上可能会出现整型溢出的情况

所以我们最好这样写mid = left + (right - left) / 2;

我们以升序数组为例

如果nums[mid]比target大，证明target在[left, mid]这个区间中

这里也有一个易错点很多人会将right = mid这是错误的

这样赋值会造成死循环

正确的写法应该是right = mid - 1;

因为我们已经证明了nums[mid]比target还要大，所以target至少是从mid - 1开始取值

如果nums[mid] < target left = mid + 1;

如果等于就直接返回，如果没有找到就返回-1;

三、代码

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