网站用php与asp哪个好,大连开发区网站建设,前端开发入门培训,安卓小项目源码免费网站LeetCode刷题第一题#xff1a;704二分查找法 什么是二分查找#xff1f;题目思路和边界问题 参考
代码随想录 什么是二分查找#xff1f;
二分查找#xff08;Binary Search#xff09;是一种在有序数组中查找特定元素的查找算法。它通过将目标值与数组的中间元素进行比… LeetCode刷题第一题704二分查找法 什么是二分查找题目思路和边界问题 参考
代码随想录 什么是二分查找
二分查找Binary Search是一种在有序数组中查找特定元素的查找算法。它通过将目标值与数组的中间元素进行比较并根据比较结果缩小查找范围直到找到目标值或确认目标值不存在为止。
一般步骤如下
确定查找范围的起始点和结束点。计算中间元素的索引并取得中间元素的值。将目标值与中间元素的值进行比较。如果目标值与中间元素相等查找成功返回中间元素的索引。如果目标值小于中间元素的值说明目标值可能在左半部分将查找范围缩小为左半部分。如果目标值大于中间元素的值说明目标值可能在右半部分将查找范围缩小为右半部分。重复步骤2至步骤6直到找到目标值或确定目标值不存在。
二分查找是一种高效的查找算法时间复杂度为O(log n)其中n是数组的元素个数。但前提是要求数组必须是有序的。
题目
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 样例输出
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 思路和边界问题
二分查找涉及的很多的边界条件逻辑比较简单但就是写不好。例如到底是 while(left right) 还是 while(left right)到底是right middle呢还是要right middle - 1呢
写二分法区间的定义一般为两种左闭右闭即[left, right]或者左闭右开即[left, right)。
二分法第一种写法 第一种写法我们定义 target 是在一个在左闭右闭的区间里也就是[left, right]
区间的定义这就决定了二分法的代码应该如何写因为定义target在[left, right]区间所以有如下两点
while (left right) 要使用 因为left right是有意义的所以使用 if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1 代码实现
//i want to武动乾坤
class Solution {
public:int search(vectorint nums, int target) {int left0,rightnums.size()-1;//这里使用了闭区间。int model0;//定义中间位置while(leftright){int modelleft((right-left)/2);//这里是为了防止溢出if(nums[model]target){rightmodel-1;}else if(nums[model]target){leftmodel1;}else{//否则就是所求的值等于了model位序对应的元素return model;//返回所找到的序号}}return -1;//如果循环了一遍发现要找的元素没有找到返回-1}
};第二种方法 如果说定义 target 是在一个在左闭右开的区间里也就是[left, right) 那么二分法的边界处理方式则截然不同。
有如下两点
while (left right)这里使用 ,因为left right在区间[left, right)是没有意义的 if (nums[middle] target) right 更新为 middle因为当前nums[middle]不等于target去左区间继续寻找而寻找区间是左闭右开区间所以right更新为middle即下一个查询区间不会去比较nums[middle] class Solution {
public:int search(vectorint nums, int target) {int left0,rightnums.size();//这里使用了左闭右开区间所以让rightnums.sizeint model0;//定义中间位置while(leftright){int modelleft((right-left)/2);//这里是为了防止溢出if(nums[model]target){rightmodel;//从0到model}else if(nums[model]target){leftmodel1;//左闭所以这里的model小于目标值。}else{//否则就是所求的值等于了model位序对应的元素return model;//返回所找到的序号}}return -1;//如果循环了一遍发现要找的元素没有找到返回-1}
};
