Day1-数组

Leetcode704 二分查找

初解

已经不记得二分查找了，遍历找O(n)其实也过了，只是借此复习一下二分，确实快很多。
二分的前提条件题目里也都明示了：无重复，（从小到大）排序。我没有用到这个条件，自然时间复杂度高于最优解。

看完解答

我再看了一眼题目的标题，才知道是考BinarySearch嗯嗯啊啊，数算的一个小小算法已经忘记干净了。当然二分是非常实用的，解答里很贴心地喂了两种情况和模板，我默写一下：（默认从小到大排，数组叫sum，待查找数值为val）

闭区间[l,r]

1.while()里面是l<=r，因为这是有意义的（最后剩一个）。
2.取中点之后，若sum[mid]<val，即目标区间缩小为右半边，就要改动左端点为mid+1，保证下一次循环还是闭区间。

开区间[l,r)

第一点：while()里面是l<r。
第二点：取中点之后，若sum[mid]<val，即目标区间缩小为右半边，就要改动左端点为mid+1，保证下一次循环还是左闭右开；若sum[mid]>val，即目标区间缩小为左半边，就要改动右端点为mid，保证下一次循环还是左闭右开。

其实用表格就可以解决了（但是我不会快速建表插件之外的建表方法），精髓就是注意在循环中保持区间性质不变，还有出口。

小技巧：防止l+r溢出，写mid=l+(r-l)>>1;