千锋教育web前端高频面试题视频教程，kerwin大话前端面试秘籍（附答案）

二分搜索

一，查找

顾名思义就是大家常说的增删改查中的查，想要在某一个数据结构内查找某个元素。

二，二分搜索思想

二分搜索其实就是二分查找。

1. 取搜索序列的中间元素为此次搜索的对比元素，与待搜索元素进行比较。如搜索序列有偶数个元素，那么可以以中间两个元素的其中一个作为此次对比元素，通常选左边那个

2. 如果此次对比元素较大，说明搜索元素只能在这个对比元素的左侧，对左侧序列继续进行二分搜索

3. 如果此次对比元素较小，那么搜索元素只能在这个对比元素的右侧，对右侧序列继续进行二分搜索

4. 如果此次对比元素与搜索元素相等，那么搜索成功了。

5. 直到初识序列完成递归，然而还是没有搜索成功，那么此序列中便没有这个搜索元素，意味着搜索失败。

三，性能

因为二分搜索省去了很多不必要的比较，直接从大或小的序列中进行下次搜索，所以性能还是比较好的

通过查找树容易发现，时间复杂度是O(log2(n))

四，适用情况

此方法只能对已经有序的序列进行使用。