Binary Search

[toc] 二分查找 时间复杂度O(log n) 解析 存在一个有序数组 array = [1, 3, 6, 10, 13, 20, 21, 40, 50, 55] len: 10 需要查询的6的位置 当第一次查找时,根据长度计算需要二分的下标 10/2 = 5, 即获取到下标为5的值为 20 20 > 目标值,则取左侧 再次执行 下标计算 5/2 = 2, 下标为2的值 6, 是目标值,则返回。 再次执行… 总结 n * (1/2)^k = 1 ==> 2^k = n ==> log(n) k 以为底的 平横二叉树与二分查找时间复杂度一样O(log n), 平衡二叉树在内存上是逻辑连续或者连续的。 以上数组在内存是一块连续的内存。...