九章算法第二天，二分搜索

二分搜索分两类，一类可以直接看出来是二分搜索

另一类很难直接看出来是二分搜索，

最重要的是理解二分搜索的思想，

根据有序集合这个特性，每次通过O(1)的时间复杂度，使得搜索的规模减半，

同红黑树查找类似（红黑树也是在增加了空间复杂度的情况下，减少了时间复杂度，每次比较，然后就会使得搜索规模减半）

九章讲的二分模板，我觉得比较好，这样在写代码的时候不会犯错造成死循环，而且可以处理两个整数相加溢出的问题

------------

public class Solution {
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return an integer
     */
    public int lastPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {//start +　1 < end 
            int mid = start + (end - start) / 2;//处理了整数溢出
            if (nums[mid] == target) {
                start = mid;
            } else if (nums[mid] < target) {
                start = mid;
                // or start = mid + 1
            } else {
                end = mid;
                // or start = mid - 1
            }
        }
        
        if (nums[end] == target) {
            return end;
        }
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }
}

首先解释下为什么是 start+1 < end，其实我们做二分搜索的时候，每次解空间的计算规模都会减半，

最终结束的条件我们可以认为是 start 与 end相邻就可以不再计算了(因为要么就是start 要么就是end，这样一来不会出错，二来也比较好理解)，这样最后我们判断的时候 end start都判断一次是否我们想要的解即可

这样就不会遗漏情况

下面的代码是我第一次自己想出来的解法，求解的方式是先二分找一次，找完之后接着递归再在当前解的右边再次二分搜一次，如果搜不到那么之前的解便是最后的目标值

比较蠢，但还是通过了，上完课之后对二分理解更加深刻了，就不会用这种思路了

    public int lastPosition(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }

        int position = Arrays.binarySearch(nums,target);
        if (position < 0){
            return -1;
        }
        int lastPosition = position;
        do{
            position = Arrays.binarySearch(nums,position+1,nums.length,target);
            if (position >= 0){
                lastPosition = position;
            }
        }while (position >=0);

        return lastPosition;
    }

现在讲一个寻找旋转数组的最小值

题意大概是类似这样的有序数组 [0,1,2,4,6,7] 旋转成[4,6,7,0,1,2] 然后让你找到最小值假设没有重复值

这题其实比较trick ，如果注意的话就发现了一个规律如下图

就是 0-2这个有序集合，它是不会大于4-7的集合

而我们的最小值就在第二条直线的起始处

这样我们就可以假设mid的两种情况，

如果mid落在左边的集合，很显然，左边这个集合的所有值都是大于整个大的集合的最后一个元素 2

这个时候我们让start = mid 等于就把问题的规模减半了（例如图二）

图1

图2

------------------------------------------------

寻找峰值的思想是类似的，类似股票的K线，左边是上升，右边是下降，找到中间的任意一个峰值点即可

因为是找到任意一个峰值点，所以这里最主要的是要分析如何二分，

九章算法第二天，二分搜索

推荐阅读