二分查找和二分答案

简介: 二分查找和二分答案

二分查找(Binary Search)和二分答案(Binary Search for Answer)是两种不同的算法思想,尽管它们都基于分治策略,但应用场景和目的有所不同。


二分查找(Binary Search)


二分查找是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两半,通过与目标值的比较,缩小搜索范围,逐步逼近目标值,直至找到或确认不存在。二分查找的时间复杂度为O(log n),极大地提高了在大数据集中的搜索效率。


二分答案(Binary Search for Answer)


二分答案是一种解决问题的策略,主要用于解决那些答案区间已知(通常是连续的数值区间),且问题具有单调性(即随着答案增大或减小,问题的性质不变或有规律变化)的问题。其核心思想是不断猜测问题的解(通常取区间的中点作为猜测值),根据猜测值计算出的结果与期望结果的比,来调整搜索区间(如果计算结果偏大,则在左半区间继续搜索;反之,在右半区间搜索)。这个过程重复,直到找到精确解或达到预定的精度要求。二分答案常用于解决最优化问题,如寻找满足特定条件的最小区间、最大值、最小值等,其时间复杂度同样为O(log n)。


区别


应用场景:二分查找适用于已排序的数组中查找元素;二分答案则适用于求解满足特定条件的最优解,特别是当解的范围已知且解空间存在单调性时。

目的:二分查找旨在直接找到某个确定的元素;二分答案旨在逐步逼近并找到满足条件的最佳解或边界。

数据结构依赖:二分查找依赖于有序数组或可进行类似有序访问的数据结构;二分答案则不一定依赖于特定数据结构,更多依赖于问题本身的性质。


这两种算法都体现了分而治之的策略,通过不断缩小问题规模来高效解决问题


目录
相关文章
|
2月前
|
人工智能 算法 C语言
详解树状数组(C/C++)
详解树状数组(C/C++)
|
7月前
|
算法 索引
二分查找与二分答案
二分查找与二分答案
|
7月前
|
算法 测试技术 C#
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
|
7月前
|
算法 NoSQL 容器
二分查找 三分查找与二分答案
二分查找 三分查找与二分答案
|
7月前
|
存储 算法
03 折半查找
  折半查找又称为二分查找。它仅适用于有序的顺序表。   折半查找的基本思想:首先给定值 key 与表中中间位置的元素比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若给定值 key 大于中间元素,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找,如此重复,知道找到位置,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。  
48 0
|
算法 测试技术 C++
C++算法:二分查找旋转数组
C++算法:二分查找旋转数组
|
算法 C语言 C++
【双指针问题】977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
57 0
|
机器学习/深度学习 存储 人工智能
“二分“==“二分查找“ ?“yes“:“no“;
“二分“==“二分查找“ ?“yes“:“no“;
128 0