8

二分法

二分法是针对的有序的序列，我们将要找的数字跟这个区间内的中位数进行比较，然后确定是做区间还是右区间，这点倒是很像分治的思想，例如快排中选择一个基点然后左右排列，递归，所以二分法很像分治的思想。

二分查找的不可用的地方

• 数据太少，直接遍历即可

• 无序 如果是无序应该先排序再查找

• 频繁进行io 这样的话就需要经常的排序，

• 数据必须是顺序表不能是链表

• 数据量太大也不行 因为 这么大的数组内存放不下啊。

时间复杂度

很明显每次都是对折如果我们反过来看从1开始每次都是2倍自己那么我们可以得到的是2^k = n 很明显是指数，所以当我们从n然后推出k的时候 也很明显了，就是用的指数的对边 --- 对数 所以它的时间复杂度就是 log2n 我们可以简称为 logn 而且没有任何的其它项，所以说，这就是为什么 二分法比某些O(1)还要快的原因 --- O(1)有可能常数项是100000 但是 log2n就比这个数字小的多.

二分法的变形算法

• 查找第一个值等于给定值的元素

• 查找最后一个值等于给定值的元素

• 查找第一个大于等于给定值的元素

• 查找最后一个小于等于给定值的元素