15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能

作者：鲁米

2023-12-07
北京
本文字数：755 字
阅读完需：约 2 分钟

如何编程实现“求一个数的平方根”？要求精确到小数点后 6 位。

public class SqrtExample {
    public static double sqrtWithPrecision(double number, int precision) {        double result = Math.sqrt(number);        BigDecimal bd = new BigDecimal(result);        bd = bd.setScale(precision, BigDecimal.ROUND_HALF_UP);        return bd.doubleValue();    }
    public static void main(String[] args) {        double number = 25;        int precision = 6;        double result = sqrtWithPrecision(number, precision);        System.out.printf("The square root of %.2f is approximately %.6f%n", number, result);    }}

复制代码

我刚才说了，如果数据使用链表存储，二分查找的时间复杂就会变得很高，那查找的时间复杂度究竟是多少呢？如果你自己推导一下，你就会深刻地认识到，为何我们会选择用数组而不是链表来实现二分查找了。

1. 二分查找的思想： 二分查找通过比较中间元素的值来缩小搜索范围。在数组中，可以通过索引直接访问中间元素；然而，在链表中，需要遍历链表来找到中间节点，这需要 O(n) 的时间。

2. 查找过程： 对于链表，每次找到中间节点都需要遍历一半的链表长度。第一次查找需要遍历 n/2 个节点，第二次需要遍历 n/4 个节点，以此类推。总的遍历次数是 log n（以 2 为底），因此查找的时间复杂度是 O(n * log n)。

3. 数组 vs 链表： 在数组中，通过索引可以直接访问任意位置的元素，而在链表中，需要遍历指定数量的节点来到达目标位置。这导致链表上的二分查找效率不如数组，因为链表无法直接跳跃到中间节点。

由于二分查找在链表中的效率较低，一般情况下，我们更倾向于在有序数组上应用二分查找算法，而不是在链表上应用。链表更适合线性查找或其他更适合遍历的算法。

发布于: 刚刚阅读数: 5

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。

发布

暂无评论

创作场景

15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能

鲁米

评论