二分查找

题目

用 Javascript 实现二分查找（针对有序数组），说明它的时间复杂度

一个故事

N 年前，百度，一个复杂的后台系统出现了问题，因为太大找不到问题所在。 一个工程师，使用二分法，很快找到了问题原因。

无论多么大的数据量，一旦有了二分，便可快速搞定。
二分法，是算法的一个重要思维。

但二分法有一个条件：需要有序数据。

分析

二分查找是一种固定的算法，没什么可分析的。

两种实现思路

• 递归 - 代码逻辑更加简洁
• 循环 - 性能更好（就调用一次函数，而递归需要调用很多次函数，创建函数作用域会消耗时间）

时间复杂度 O(logn)

答案

参考 binary-search.ts 和 binary-search.test.ts

划重点

• 有序，就一定要想到二分
• 二分的时间复杂度必定包含 O(logn)