while( start + 1 < end ){
    mid = start + ( end - start ) / 2
    if(num[mid] == target) return mid
    else if(num[mid] > target) end = mid - 1 // 也可为 end = mid
    else if(num[mid] < target) start = mid + 1 // 也可为 end = mid
}
if(num[start] == target) return start
if(num[end] == target) return end

(start + end + 1)/2, 结果偏右； (start + end)/2, 结果偏左。但两者都可能产生死循环， 解决方法 => while( start + 1 < end )

int lower_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l <= r) {
        int mid = (r-l)/2+l;
        if (nums[mid] < target)
            l = mid+1;
        else
            r = mid-1;
    }
    return l;
}

1. 二分数组
2. OOXX: 二分没有终点的数组, 找到满足条件的第一个/最后一个位置
3. Half and Half: 没有明确的XXOO关系， 但可以缩小范围， e.g. Find Peak Element
4. 二分值域: minimization maximization problems are solved with BS in most of the cases

• bisect_left: 插入位置，若已经存在，则返回最左已经存在的位置
• bisect_right:插入位置，若已经存在，则返回已经存在的位置的后一格

278. First Bad Version
497. Random Point in Non-overlapping Rectangles

讲矩形面积化为presum array, 产生随机数[0, total area - 1], 二分找到随机数对应的矩阵，并由余数计算具体哪个点。*面积=(y2 - y1 + 1) * (x2- x1 + 1)

302. Smallest Rectangle Enclosing Black Pixels

极其痛苦！用二分法分别左右上下的边界，如找左边界->第一个col中含有1，右边界->第一个col中不含有1，两者可以合并成一个二分方程，满足条件第一个col中含有1==True/False，同理可找到上下边界。

74. Search a 2D Matrix化为一维数组做（若没有每行最后数字<下一行第一个数字的限制，那么从左下角开始linear scan)
240. Search a 2D Matrix II
658. Find K Closest Elements二分查找左端点的位置，若x-nums[m]>nums[m+k]-x,则右移
981. Time Based Key-Value Store
2300. Successful Pairs of Spells and Potions对于每个spell, 二分查找position中最小开始位置\

• 先从l=0,r=1开始逐渐增长l,r(l=r, r*=2)直至[l,r]符合条件。再用一般二分法解。

702. Search in a Sorted Array of Unknown Size
300. Longest Increasing Subsequence单调栈+replace larger value within the stk

153. Find Minimum in Rotated Sorted Array因为递增，若nums[m]>nums[r],则右边不是单增，有最小值，否则左边有最小值
154. Find Minimum in Rotated Sorted Array II解决dup的方法，每步移动左右指针直至nums[m]!= nums[l]!=nums[r]，然后采用和153一样的方法
33. Search in Rotated Sorted Array同153,判断哪段是有序的+target是否在有序区间内
81. Search in Rotated Sorted Array II同154，每步移动左右指针直至nums[m]!= nums[l]!=nums[r]
162. Find Peak Element只需比较nums[m]<nums[m+1]即可
34. Find First and Last Position of Element in Sorted Array共用二份函数，分isFirst=T/F两个选项
2055. Plates Between Candles

类似于34，设candle[]记录每个candle的指数，二分法找到左右端点i,j，则candle[j] - candle[i] -(j-i)即为当中盘子的个数

4. Median of Two Sorted Arrays

将A,B两数列切成两部分，s.t. leftA<rightB && leftB < rightA，且leftA+leftB的size正好为一半。若A的partition可确定，则B的也自然推得。前者由二分法确定, 且令A的尺寸较小；若A的指针pa,或B的指针pb移动到边界，则设leftA=inf/-inf，同理leftB

378. Kth Smallest Element in a Sorted Matrix

值域二分m[0][0], m[-1][-1]间的数，判断矩阵中有多少数<=该数（从左下开始向右直至<target,->向上->向右->...，每次向右时加上该列所在位置之上的元素个数(参考240. Search a 2D Matrix II`

878. Nth Magical Number

值域二分[1,min(a,b)*n], 判断val//a + val//b - val//lcm(a,b)是否小于n；同xxoooo, 算法会返回val//a + val//b - val//lcm(a,b)>=n的最小值，故一定是magic number.

719. Find K-th Smallest Pair Distance值域二分+双指针
875. Koko Eating Bananas
2141. Maximum Running Time of N Computers值域二分；每个电池的使用=min(battery, target),若加起来<target*n,则无法达到target；一个电池若>target,多出的电量也无法被用到别的电脑上
1802. Maximum Value at a Given Index in a Bounded Array当呈现单峰山形状时，可以达到maxValue， 值域二分每个num[index]，使其面积最接近但不超过maxSum
2513. Minimize the Maximum of Two Arrays满足val-val//d1>= cnt1, val-val//d2>=cnt2, and 能不同时被d1, d2整除的个数 val-lcm>=cnt1+cnt2
2616. Minimize the Maximum Difference of Pairs\

排序，值域二分max diff: 从左至右linear scan可以判断是否有nums[i+1]-nums[i]>= target, 若满足i+=2,因为greedy保证此方法只会挑选到最左边的，e.g.(i, i+1) vs. (i+1, i+2)，左边的选择总能保证剩下更多以供选择;否则i+=1

2812. Find the Safest Path in a Grid1）用bfs得到每个点的safeness factor 2)值域二分

2981. Find Longest Special Substring That Occurs Thrice I 2560. House Robber IV

74. Search a 2D Matrix化为一维数组做（若没有每行最后数字<下一行第一个数字的限制，那么从左下角开始linear scan
240. Search a 2D Matrix II从左下开始向右直至<target,->向上->向右->...，
162. Find Peak Element

从任意边界开会往叫大致爬， dfs， 最坏O(n^2) 从中间行找到其中最大值->往高处爬（不肯返回中间行，所以搜索区域减半，选较大一半，继续找中间行二份，直至只剩三行o(mlgn) 若用上面二分法，但依次行列减半，则可降为o(n),implement更为繁琐。