力扣

二分查找初级模板（确认有无元素）

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

二分查找寻找边界模板（找到满足条件的最小值）

int l = 1, r = max;
while(l < r) {
    int mid = l + (r - l) / 2;
    if(满足条件) r = mid;
    else l = mid + 1;
}
return l;

**374. 猜数字大小（基本题）**

public int guessNumber(int n) {
    int l = 1, r = n;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(guess(mid) == 0) return mid;
        else if(guess(mid) == -1) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

**2300. 咒语和药水的成功对数（第一个大于等于x的元素）**

public int[] successfulPairs(int[] spells, int[] potions, long success) {
    // 将药水数组按升序排序
    Arrays.sort(potions);
    // 获取咒语数组的长度，并创建一个数组来存储答案
    int n = spells.length;
    int ans[] = new int[n];
    // 对于每个咒语，计算需要的药水值，并使用二分查找来查找大于或等于该值的药水数量
    for(int i = 0; i < n; i++) {
        double x = success * 1.0 / spells[i];
        ans[i] = binarySearch(x, potions);
    }
    return ans;
}

// 使用二分查找算法来查找大于或等于给定值x的药水数量
public int binarySearch(double x, int[] potions) {
    int n = potions.length;
    int l = 0, r = n;
    
    while(l < r) {
        int mid = l + (r - l) / 2;
        // 如果大于等于就r = mid
        if(potions[mid] >= x) r = mid;
        // 否则l = mid + 1这是为了保证不出现死循环
        else if(potions[mid] < x) l = mid + 1;
    }
    
    // 返回大于或等于x的药水数量
    return n - l;
}

**875. 爱吃香蕉的珂珂（查找第一个小于x的元素）**

public int minEatingSpeed(int[] piles, int h) {
    // 找最大值
    int max = 0;
    for(int x: piles) 
        max = Math.max(x, max);
    int l = 1, r = max;
    while(l < r) {
        int mid = l + (r - l) / 2;
        // 检查能不能吃完，能吃完就减小速度，不能吃完就加大速度
        if(check(mid, piles, h)) r = mid;
        else l = mid + 1;
    }
    return l;
}
boolean check(int k, int[] piles, int h) {
    int sum = 0;
    for(int x: piles) {
        int remainder = x % k;
        sum += x / k;
        if(remainder != 0) sum++;
    }
    // 如果总共花的时间小于等于h则吃完，否则吃不完
    return sum <= h;
}

**162. 寻找峰值（特殊思路二分查找）**

public int findPeakElement(int[] nums) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while(l < r) {
        int mid = l + (r - l) / 2;
        // 如果比右侧大，可能是山峰
        if(nums[mid] > nums[mid + 1]) r = mid;
        // 否则该点不能是山峰，搜索右区间
        else l = mid + 1;
    }
    // 出来的条件一定是l == r
    return l;
}