当前位置：首页 > 范文大全 > 实用文>二分查找的一些注意事项

二分查找的一些注意事项

2023-04-06 07:56:31 收藏本文下载本文

“常璀错”通过精心收集，向本站投稿了3篇二分查找的一些注意事项，下面是小编帮大家整理后的二分查找的一些注意事项，欢迎阅读，希望大家能够喜欢。

二分查找的一些注意事项

篇1：二分查找的一些注意事项

二分查找作为O(log(n))时间复杂度的查找算法得到了广泛的使用，

1.在已排序的数组中查找特定的元素。或者是满足条件的第一个元素

2.数学常用的求解方程的解，也是数学家所指的对半查找。

3.程序调试中用来定位错误语句

4….

篇2：二分查找的一些注意事项

针对上文代码中

mid=(left+right)/2;

这一句代码有两个注意事项：

1.计算机方式有乘以2n或者是除以2n都可以利用移位代替。所以上述代码可以改为：

mid=(left+right)>>1;

2.第二个需要注意的是该段代码有可能产生溢出。当数组的中元素个数很多时候，至少大于INT_MAX2,当left和right都是接近INT_MAX.二者相加就可能得到一个负数。这种办法有两个。

2.1将mid定义成

long long mid;

2.2

mid=left+(right-left)/2;

篇3：二分查找的一些注意事项

这里在leetcode上找了一个应用来说明问题

链接地址leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

题目：

Follow up for “Find Minimum in Rotated Sorted Array”:

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

class Solution {public: int findMin(vector& nums) { if(nums.empty())return 0; int left=0,right=nums.size()-1,mid; while(nums[left]>=nums[right]) {mid=(left+right)>>1;if(nums[mid]>nums[right]) left=mid+1;else if(nums[left]>nums[mid]) right=mid;else if(nums[left]==nums[mid]&&nums[right]==nums[mid]){ int tmp=nums[left]; for(int i=left;inums[i])tmp=nums[i]; return tmp;} } return nums[left]; }};

本人在写上述代码时候就是放了第二个错误。

left=mid+1; right=mid;

只要有一个常数步就可以在邻近的两个元素避免死循环。

【二分查找的一些注意事项】相关文章：