二分查找

二分查找(Binary Search),二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

问题思考

  1. 假设我们有 1000 万个整数数据,每个数据占 8 个字节,如何设计数据结构和算法,快速判断某个整数是否出现在这 1000 万数据中?
  2. 有序的数据集合
  3. 二分查找的递归实现
  4. 二分查找的非递归实现
  5. 二分查找的限制
    • 二分查找依赖的是顺序表结构,简单点说就是数组。主要原因是二分查找算法需要按照下标随机访问元素。
    • 二分查找针对的是有序数据。所以,二分查找只能用在插入、删除操作不频繁,一次排序多次查找的场景中。针对动态变化的数据集合,二分查找将不再适用。
    • 数据量太小不适合二分查找。
      • 不过,这里有一个例外。如果数据之间的比较操作非常耗时,不管数据量大小,都推荐使用二分查找。
    • 数据量太大也不适合二分查找。
      • 二分查找的底层需要依赖数组这种数据结构,而数组为了支持随机访问的特性,要求内存空间连续,对内存的要求比较苛刻。
  6. 如何编程实现“求一个数的平方根”?要求精确到小数点后 6 位。
  7. 如果数据使用链表存储,二分查找的时间复杂就会变得很高,那查找的时间复杂度究竟是多少呢?
  8. 常见二分查找变形问题:
    • 查找第一个值等于给定值的元素
    • 查找最后一个值等于给定值的元素
    • 查找第一个大于等于给定值的元素
    • 查找最后一个小于等于给定值的元素
  9. 凡是用二分查找能解决的,绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省,但是毕竟内存如此紧缺的情况并不多。

You may also like...

1 Response

  1. zclmoon说道:

    hello world!

发表评论

电子邮件地址不会被公开。 必填项已用*标注