[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), 平衡二叉树在内存上是逻辑连续或者连续的。 以上数组在内存是一块连续的内存。也就是说明了数组查找快的原因，只需要移动内存的指针即可找到下一个