学习二分查找

张开发
• 2026/4/19 22:34:44 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

学习二分查找
一什么是二分查找二分查找是一种在有序数组中快速查找目标值的算法。核心思想就是每次把查找的区间减半用中间值判断目标值再左还是在右然后不断缩小区间范围。前提条件数组必须有序注升序降序都行二关于二分查找的时间复杂度时间复杂度Olog n 注比暴力O(n)快得多且数据越大越明显。空间复杂度O1非递归三主要的二分模版#includeiostream #includealgorithm using namespace std; int a[100010]{0}; int main(){ int n,m; cinnm; for(int i1;in;i){ cina[i]; } sort(a1,an1); int x; while(m--){ cinx; int left1; int rightn; int mid; bool totfalse; while(leftright){ midleft(right-left)/2; if(xa[mid]){ tottrue; break; }else if(xa[mid]){ rightmid-1; }else if(xa[mid]){ leftmid1; } } if(tottrue){ coutYES\n; }else{ coutNO\n; } } return 0; }有些关键点1midleft(right-left)/2会比(rightleft)/2更安全防止int数据类型溢出。2就是循环条件leftright。情况一当然循环条件可以有选择的使用常用的是小于等于是为了方便查找目标值是否存在。查找区间也是[left,right]。逻辑当leftright时区间里还有最后一个元素需要检查此时如果不检查就会漏掉这个元素。情况二这个情况也是特殊情况应为有些题会让你找数组边界这个时候可以用leftlight一般这样的题数组区间是左开右闭合[left,right)不包含right逻辑循环结束时leftlight返回left就是答案或返回right。总结二分查找就是有序减半判断缩边。

更多文章