二分算法

• 二分

  • 整数二分

    • 模板

  • 浮点数二分

二分

整数二分

整数二分分为两种，一种找最左边的，一种找最右边的。

模板

最左边

public int search (int[] nums, int target) {
  if(nums == null || nums.length == 0){
    return -1;
  }
  int l = 0, r = nums.length - 1;
  while(l < r){
    int mid = l + r >> 1;
    if(nums[mid] >= target){
      r = mid;
    }else{
      l = mid + 1;
    }
  }
  return nums[l] == target ? l : -1;
}

最右边

public int search (int[] nums, int target) {
  if(nums == null || nums.length == 0){
    return -1;
  }
  int l = 0, r = nums.length - 1;
  while(l < r){
    int mid = l + r + 1 >> 1;
    if(nums[mid] <= target){
      l = mid;
    }else{
      r = mid - 1;
    }
  }
  return nums[l] == target ? l : -1;
}

浮点数二分

public void search(double l, double r){
	double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

借鉴Acwing算法模板