LeetCode-＞二分法(三)

搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       while(left<right){
           int middle = left+(right-left)/2;
           if(nums[middle]>=target){
               right = middle;
           }else{
               left = middle+1;
           }
       }
       if(target>nums[nums.length-1]){
           return nums.length;
       }else{
           return left;
       }

    }
}

这道题就是不断用二分法逼近最靠近target的值,但是我们还需要注意的一点就是,当我们数组的最后一个值比target还要小的时候那么我们就需要返回nums.length->因为我们二分法是在0~nums.length进行寻找的.

---

山脉数组的峰顶索引

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            int middle = left+(right-left+1)/2;
            if(arr[middle-1]<arr[middle]){
                left = middle;
            }else{
                right = middle-1;
            }
        }
        return left;
    }
}

这道题也是利用逼近的想法,不断找到逼近山峰,

但是注意middle= left+(right-left+1)/2;和left= middle->配套使用,防止出现死循环.