Leetcode ｜ Binary search | 22. 74. 162. 33. 34. 153.

22. Generate Parentheses

要意识到只要还有左括号，就可以放到path里。只要右括号数量小于左括号，也可以放进去。就是valid的组合。recurse两次

74. Search a 2D Matrix

看成sorted list就好。直接用m*n表示最后一位的index，并且每次只需要

int x = mid / n;

int y = mid % n;

就可以算出位置。

值得注意的是左闭右开和左开右闭的写法

162. Find Peak Element

当一个middle不是peak的时候，middle和旁边的两个element有三种可能：单增，单减，波谷

单增/单减的话，比middle大的那边是有可能有peak的，因为如果增大再在某处减小，就有peak，如果一直增大，那么在起头/结尾的地方会有peak因为 nums[-1] = nums[n] = -∞

波谷的话，随便走一边就行

注意处理mid在最开始和最后的情况，mid-1和mid+1有的时候不valid。比如mid-1不valid的情况，就要看mid+1是不是大于mid，如果是的话就废了，如果不是就是peak（当然本题不会出现废了的情况，因为一定有peak）

33. Search in Rotated Sorted Array

 把这个图画出来。

先比较start和mid，判断mid落在左边还是右边。

如果是左边，那么当taregt大于mid和当target太小了到小于start的程度，start就应该为mid+1

如果是右边，那么当target小于mid和当target太大了到大于end-1的程度，end就应该为mid

34. Find First and Last Position of Element in Sorted Array

lowerbound 方法：

 如果lowerbound不存在（没有比target大于等于的数字）那么直接-1，-1

如果存在，那么检查target的lowerbound是不是target，如果不是，-1，-1

如果是，那么target的lb就是左边界，target+1的lb再减1就是右边界

lowerbound咋写？背下来得了。

变化1：mid==target的时候与target<mid一样的选择

变化2:返回left

and下面这个方法不太理解。？

153. Find Minimum in Rotated Sorted Array

先判断是否处在一个单增的线上，如果是的话直接返回left就行。

如果不是，那么如果mid在左半边较大的线上（mid>=start），那么start = mid+1只在右边找

如果mid在右半边线上，最小值只会在左边。end=mid（因为有可能mid本身就是最小值）。