网站 手机 app,c 还可以做网站,wordpress文章前台看不到,中山网站建设品牌目录
什么是二分查找 一、左闭右闭写法[left,right] 代码演示#xff1a;
二、左闭右开写法[left,right]
代码演示#xff1a; 今天进行了二分查找的学习。
什么是二分查找 二分查找#xff08;Binary Search#xff09;是一种常用的搜索算法#xff0c;也被称为折…目录
什么是二分查找 一、左闭右闭写法[left,right] 代码演示
二、左闭右开写法[left,right]
代码演示 今天进行了二分查找的学习。
什么是二分查找 二分查找Binary Search是一种常用的搜索算法也被称为折半查找。它用于在已排序的数组中查找特定元素的位置通过反复将待查找范围缩小为一半来提高效率。 以下是二分查找的一般步骤 确定搜索范围首先确定要搜索的数组的起始和结束位置。通常这是整个数组的起始和结束。 计算中间位置计算中间位置的索引即 (start end) / 2。 比较中间元素将要查找的元素与中间位置的元素进行比较。 如果要查找的元素等于中间位置的元素那么找到了目标返回中间位置的索引。如果要查找的元素小于中间位置的元素那么说明目标在左半部分将搜索范围缩小为左半部分。如果要查找的元素大于中间位置的元素那么说明目标在右半部分将搜索范围缩小为右半部分。 重复步骤2和步骤3直到找到目标元素或搜索范围为空。如果搜索范围为空说明目标元素不在数组中。 二分查找的时间复杂度为O(log n)其中n是数组的长度。这是因为每次迭代都将搜索范围缩小为一半所以在最坏情况下需要进行log n次迭代才能找到目标元素。 二分查找通常用于已排序的数组例如升序排列的整数数组或字母表中的单词。它是一种高效的查找算法适用于大型数据集。 一、左闭右闭写法[left,right] 定义target是在区间[left,right]里面的所以有如下两点middle(leftright)/2; while( left right ),应该使用,因为是一个左闭右闭的区间。例[1,1]此时while循环应当用.if( nums[middle] target )此时right应该赋值为middle-1因为当前这个nums[middle]⼀定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1 代码演示
class Solution {
public:int search(vectorint nums, int target) {int left 0; // 定义左边界int right nums.size() - 1; // 定义右边界while (left right) {int middle left (right - left) / 2; // 计算中间位置避免整数溢出if (nums[middle] target) {return middle; // 找到目标返回索引} else if (nums[middle] target) {right middle - 1; // 目标在左半部分更新右边界} else {left middle 1; // 目标在右半部分更新左边界}}return -1; // 如果未找到目标元素}
};在计算中间位置时一种最直观的方法是使用 (left right) / 2。然而这种方式在极端情况下当 left 和 right 很大时可能会导致整数溢出问题这会导致程序错误。 为了避免整数溢出我们使用了 (right - left) / 2而不是 (left right) / 2 来计算中间位置。这样做的原因是(right - left) 表示了左边界和右边界之间的距离然后除以2得到的结果就是中间位置相对于左边界的偏移量。这个偏移量被加到左边界上从而得到中间位置。 这种方式确保了中间位置的计算不会导致整数溢出因为它始终处理整数边界的相对偏移量而不是绝对值。这在处理大数组时特别重要以确保算法的正确性。 二、左闭右开写法[left,right] 定义 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 left 0; // 定义左边界int right nums.size(); // 定义右边界注意这里是 nums.size()不再减1while (left right) {int middle left (right - left) / 2; // 计算中间位置避免整数溢出if (nums[middle] target) {return middle; // 找到目标返回索引} else if (nums[middle] target) {right middle; // 目标在左半部分更新右边界不再减1} else {left middle 1; // 目标在右半部分更新左边界}}return -1; // 如果未找到目标元素}
};写在最后以上就是本篇文章的内容了感谢你的阅读。如果感到有所收获的话可以给博主点一个赞哦。如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
tips:学于代码随想录
