Search Insert Position

//递归
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l=0, r=nums.length-1;
        if (nums[l] >= target)
            return 0;
        if (nums[r] < target)
            return r+1;
        if (nums[r] == target)
            return r;
        return bs(nums, target, l, r);
    }
    private int bs(int[] nums, int target, int left, int right){
        if (right-1 == left && nums[left] < target && nums[right] >= target)
            return right;
        int mid = left + (right-left)/2;
        if (nums[mid] == target)
            return mid;
        if (nums[mid] > target)
            return bs(nums, target, left, mid);
        return bs(nums, target, mid, right);
    }
}

这个注意每次折半的时候不能丢掉mid，话说为啥空间为啥差，再写个非递归的试试。
没球区别，哭了

Peak Index in a Mountain Array

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int l = 0, r = A.length-1;
        while(l < r) {
            if (l+1 == r){
                if (A[l] > A[r])
                    return l;
                else 
                    return r;
            }
            int mid = l+ (r-l)/2;
            if (A[mid] > A[mid+1]){
                r = mid;
            } else
                l = mid;
        }
        // no way
        return l;
    }
}

这题卡了一会儿，直接mid和mid+1判断就好了，没必要和left、right比较，轴了

Find Peak Element

感觉这题是上面那题的泛化版本，思路一样，只要想明白了局部最大的存在方式就行了。。感觉有点像微积分推导局部最大值存在一样。话说二分查找不要用l+1==r这种判断方式了！！！

class Solution {
    public int findPeakElement(int[] nums) {
        int l=0,r=nums.length-1;
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]>nums[mid+1])
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
}

把上一道也重写了下，不要用l+1==r这种判断：

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int l = 0, r = A.length-1;
        while(l < r) {
            int mid = l+ (r-l)/2;
            if (A[mid] > A[mid+1]){
                r = mid;
            } else
                l = mid+1;
        }
        return l;
    }
}