google flag第一周 九章算法班第二次课 2019-03
今天搬家没来得及预习，所幸之前看过二分法的课，也基本跟上了，但还是来不及做一些提前的思考，题目都是临时看的，下次改正。
内容基本就是说二分法作为唯一的O(logn)时间复杂度的算法非常重要，基本O(n)可以优化的都是用二分法解决。
二分法有一个固定模板，基本保证不会出错，如下：
int findPosition(vector<int> &nums, int target) {
// write your code here
if (nums.empty()) {
return -1;
}
int start = 0, end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return start;
}
return -1;
}
二分法从简到难的层级分别为：
1、找到目标出现的任意位置、第一次出现的位置、最后出现的位置；
基本一样，只是对三个if的处理不一样，比如：最后一次出现，应该这样写
int start = 0, end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid;
} else {
end = mid;
}
}
2、第二境界，二分位置之XXOO，找出数组中第一个/最后一个满足条件的位置，第一境界只是找元素，故此分开
2)find k closet elements(二分+双指针算法)
3)search in a big sorted array(倍增法找到边界)
4)Find Minimum in Rotated Sorted Array(确定target的值)
5)Maximum Number in Mountain Sequence(根据升降序确定左右边界)
3、第三境界，二分位置之Half half
