笑话引入.png
二分查找作者：思路简单，细节魔鬼
1 二分查找框架
框架.png
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。
1.1 mid需要防止溢出
计算机中的计算可能会造成整型溢出从而变成负数————计算结果太大导致符号位发生不正常改变。
- 如何避免？
int mid = lo + (hi - lo) / 2;
1.2 寻找一个数
代码.png
-
细节
1）为什么while条件是小于等于
因为：对于闭区间的搜索，当区间只有一个数时候也要判断一次；
2）为什么left = mid+1，right=mid-1
因为：mid已经搜索过了
3）这个算法有什么缺陷？
如果有序数组中存在重复元素，想得到最左边或最右边的target是不可行的。
下面来讨论这两种情况：
1.3 寻找左侧边界的二分搜索
代码.png
-
细节
1）为什么条件变成小于了？
因为：本次搜索的是左闭右开区间，此时终止条件位left==right，【left，left）为空，可以正确终止。
2）为什么没有返回-1的操作？如果nums不存在target怎么办？
因为：代表返回值小于target的元素个数
2）.png
3）为什么left=mid+1，right=mid？
因为：区间是左闭右开的。
4）为什么这个算法可以搜索左侧边界？
搜索到target时候，right=mid，缩小上届。
4）.png
1.4 寻找右侧边界的二分搜索
同理：
image.png
-
细节：
1）为什么能找到右侧边界
image.png
2）image.png
3）
image.png
1.5 总结
image.png
