二分模板

「二分」模板有两套，主要是根据 check(mid) 函数为 true 时，需要调整的是 l 指针还是 r 指针来判断。

• 当 check(mid) == true 调整的是 r 时：计算 mid 的方式应该为 mid = l + r >> 1：

  long l = 0, r = 1000009;
  while (l < r) {
    long mid = l + r >> 1;
    if (check(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
  }

• 当 check(mid) == true 调整的是 l 时：计算 mid 的方式应该为 mid = l + r + 1 >> 1：

  long l = 0, r = 1000009;
  while (l < r) {
    long mid = l + r + 1 >> 1;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
  }

  

  1. 搜索旋转排序数组 II

  

  输入：nums = [2,5,6,0,0,1,2], target = 0
  输出：true

思路：

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