二分法分析

时间复杂度：最好情况下，一击命中，为常数级时间C；最坏情况下，一直二分到剩一个元素，则时间复杂度为log2N

空间复杂度：最好情况下，一击命中，不用后续递归，即不用占用调用函数时函数栈的空间，此时空间复杂度为 C

最坏情况下，一直递归二分，需要二分log2N次，即调用函数log2N次，此时空间复杂度为C * log2N

时间复杂度计算（看运行次数最多的那条语句被运行了多少次）

$O(2^n)$，表示一个算法的性能会随着输入数据的每次增加而增大两倍，典型的方法就是裴波那契数列的递归计算实现 对数阶$O(logn)$ int i = 1; while(i<n) { i = i * 2; } 上面的代码，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了，直到i不小于n退出。我们试着求解一下，假设循环次数为x，也就是说 2 的 x 次方等于 n，则由2^x=n得出x=log₂n。因此这个代码的时间复杂度为$O(logn)$

https://www.cnblogs.com/lazyegg/p/12572421.html