10.binary_search.md

二分算法（大类）

二分查找 只是一个查找算法，应用了二分思想

对顺序查找的优化

---

问题：为什么每次更新mid = mid - 1或mid + 1

因为我们每次更新的区间要保证待查找元素一定在区间里

而mid是比较过不等于target的

终止条件：l >= r;

二分的是查找区间的范围！

单次缩小一半！

二分查找--泛型情况

其实下面这两种情况都可以总结成一个

第二种可转化成第一种找第一个一的前一个位置即可

泛化：0当成条件不成立，1当成条件成立

二分查找--特殊情况

找最后的1

$min = 0, max = 9$

$mid = (min + max) >> 1 = 4$

if (arr[mid] == 1) mid = min;
//这里mid = min + 1的话就可能错过要找的值了，比如上图所示，mid = 4
// min = mid + 1 = 5直接就找不到了
else if (arr[mid] != 1) max = mid - 1;
if (mid == max) 找到结果

但是对于

$min = 4, max = 5; \ arr[min] = 1 ,arr[max] = 0$的情况$mid = 4 且 arr[mid] == 1$

mid再次更新为4，就会一直循环下去

死循环了！为了解决这个问题，同时为了在全0的数组查找1时返回-1

引入一个虚拟头指针，让min一开始 = -1

$ mid = (min + max + 1) >> 1$

if (arr[mid] == 1) mid = min;
//这里mid = min + 1的话就可能错过要找的值了，比如上图所示，mid = 4
// min = mid + 1 = 5直接就找不到了
else if (arr[mid] != 1) max = mid - 1;
if (mid == max) 找到结果

二分查找---特殊情况2

找第一个1记住缩小的是区间！

如果当前的mid == 1

那么第一个一应该在mid前，并且包括mid（mid有可能出现待查找值）

如果mid == 0 证明要查找的1肯定不在mid上啦 从mid + 1开始查

if (arr[mid] == 1) max = mid;
//找第一个1，mid刚好是第一个1舍去了就找不到了
else if (arr[mid] != 1) min = mid + 1;
if (mid == max) 找到结果

增加一个虚拟尾指针

$mid = (max + min) >> 1$

这种情况不会死循环？

增加虚拟尾指针是为了全0的时候返回一个非法值

---

二分--数组和函数的关系

数组和函数都是映射：

数组下标-> 值

函数参数-> 值

可以进行函数的求解--任何对数组应用的算法都可以应用到某种性质的函数上

三分查找---求解凹凸函数的极值

STEP1: [L, R] 为查找范围

STEP2: m1 为[L, R]的1/3处，m2为2/3处

STEP3: if (f[m1] < f[m2]) L = m1; loop SETP1-3

if (f[m2] <= f[m1]) R = m2; loop SETP1-3

else if (|m1 - m2| < exp) 终止

不管是三分还是二分，查找的原则就是不能让待查找点落在查找区间之外

此图显示了f[m1] > f[m2]的情况，m1对应着两个点，并且m1 < m2。如果此时令L = m1，那么此时就容易出现极值点就不在查找区间了。

思想就是缩小问题的求解规模