【leetcode】二分刷题=＞704、35

二分总结

二分法的前提条件：

1. 数组为有序数组
2. 数组中无重复元素：因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的

只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法

二分法的两种写法：

确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。

然后在二分查找的循环中，坚持循环不变量的原则，很多细节问题，自然会知道如何处理了。
左闭右闭即[left, right]：
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效
target 在右区间时，给left赋值middle+1，即[middle + 1, right]
target 在左区间时，给right赋值middle-1，即[left, middle - 1]

左闭右开即[left, right)：
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
target 在右区间时，给left赋值middle+1，即[middle + 1, right)
target 在左区间时，给right赋值middle，即[left, middle)

语法细节：

1、left + ((right -left) >> 1) == (left + right) /2

二进制右移
举个例子:
1010 >> 1 == 0101
1010 十进制 10
0101 十进制 5
综上 >> 1 作用相当于除二

所以 left + ((right -left) >> 1) ==> left + ((right -left)/2)
==> left + right/2 -left/2 ==> left/2 + right/2 ==> (left + right) /2
得证

问题 :为什么不直接用(left + right) /2 而用left + ((right -left) >> 1)
答: 是因为left + right 在某种情况下可能会超过基本类型所能容纳的最大值,而且 >> (位运算) 比 / 运算要快一点

二分法时间复杂度分析

查找数据长度为N，每次查找后减半，

第一次 N/2
…
第k次 N/2^k

最坏的情况下第k次才找到，此时只剩一个数据，长度为1。

即 N/2^k = 1

查找次数 k=log(N)
时间复杂度为O(logN)