Binary Search

传统算法是对有序的数通过每次查找减半的思想寻找目标数字。

思想可以拓展到对于任意给定序列，找到区分前后子序列的一种性质。重要的是三点，一是给定序列能分成前后两个子序列；二是这两个子序列能够用某性质 严格 区分开；三是无论中点落在那点，都能利用某规则判断中点是否符合性质。这个规则须与序列长度无关，通常是O(1)的。

对于传统数字排序后找特定元素的问题，特定元素把序列分成前后，前面都小于它，后面都大于； 对于findbad来说first bad是分界点，前面都是good, 后面都是bad; 对findMin和search-in-rotated-sorted来说，min为分界点，前面的皆大于等于首元素, 后面的皆小于首元素.

为什么search-in-rotated-sorted-II不能用二分？因为序列首尾可以一致，前后子序列有相同元素，不再存在某规则严格把前后子序列区分开。

这个适用范围还可以再拓展到分界点很多找其中任意一个的情况。例如findPeak, 它的peak(波)可以有很多，peak(波)之间也没有性质能把它们区分出来，乍看上去不适用于二分。但题目要求并不是找特定的peak，而是找到任意一个就行了。因此给定的数列可以划分成俩坨，前面那坨满足严格上升（题有说前后俩元素不会相等），后面那坨满足严格下降，返回的也就是个划分点peak。只是我们无法用这个方法找到特定的peak。

无论是找特定还是任意，都要满足前后两组序列的元素能够通过某种性质严格区分开这个条件。

有些看上去不能直接用二分法的题，如is subsequence, 它们的暴力解法往往超过O(n)。 这时就要想想是否存在某preprocessing能够为后面的二分法做铺垫。

还有一些比较tricky不那么容易看出怎么用二分的题，比如Kth Smallest Element in a Sorted Matrix和Find the duplicate number。虽然给定了一个数组，但它们的二分目标不是给定的数组本身，即start和end不是index, 而是数组的值的范围。我们放到后面讨论。

用STL中lower_bound的实现方法找出数组中第一个和target相等或比target大的数(当target不在时)所在的index, 即最后start/end(它们俩最后相等)所在位置.

基于此思想把模板拓展成找第一个分界点(后半边第一个元素)所在位置. 当end == nums.len时分界点看成可以是非数组内元素, 否则是在nums里. 当落在分界点前时, 把对应的start/end移到mid并加一.

适用于

1. 序列能通过某性质严格划分前和后且无论落到哪点，都能通过某与序列长度无关的（通常是O(1)的）规则判断该点是在前段还是后段, 此时让找分界点。又分为找特定分界点和找任意分界点两种情况。

2. O(n) 复杂度优化到O(lgn)

3. 查找首尾位置

时间复杂度

基本模板时间复杂度为O(lgn), 因为每次问题减半，$2^{lgn} = n$.