Day13
学习内容 : 二分查找（上）：如何用最省内存的方式实现快速查找功能？
1.无处不在的二分思想
什么是二分查找？
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
常见的二分查找：猜字游戏
2.O(logn) 惊人的查找速度
二分查找的时间复杂度：O(logn)
熟悉复杂度的推导过程
3.二分查找的递归与非递归实现
简单的二分查找：有序数组中不存在重复元素
容易出错的3个地方
- 循环退出条件
2.mid 的取值
3.low 和 high 的更新
二分查找除了用循环来实现，还可以用递归来实现
4.二分查找应用场景的局限性
二分查找只能用在数据是通过顺序表来存储的数据结构上
其次，二分查找针对的是有序数据。
再次，数据量太小不适合二分查找。
最后，数据量太大也不适合二分查找。
如何在 1000 万个整数中快速查找某个整数？
答：先对这 1000 万数据从小到大排序，然后再利用二分查找算法。
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论