首页 算法

# 二分查找

二分查找讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; 
        while (left <= right) { 
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1; 
            } else if (nums[middle] < target) {
                left = middle + 1; 
            } else {
                return middle; 
            }
        }
        return -1;
    }
};

34
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = heper(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[] {-1, -1};
        }
        int end = heper(nums, target + 1) - 1;
        return new int[]{start, end};// 简单的创建一个新的数组的方式,[start, end]
    }

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

# 以后采用的版本，左右开区间

1
2
3
4
5
6
7
8
9
10
11
12
private char binarySearch(char[] letters, char target) {
        int left = -1, right = letters.length; // (left, right)
        while(left + 1 < right) { 
            int mid = left + (right - left) / 2;
            if(letters[mid] < target) {
                left = mid;
            }else {
                right = mid;
            }
        }
        return letters[right];
    }

  1. while 循环里面的 condition 是 left + 1 < right
  2. 更新左右区间都是 right or left = mid
  3. 返回 right

# 不同类型统一化处理

以上是处理 >= 的情况

就是对应这个图里面的 right 和 left 找区间

最关键的是区间外是什么范围

test
test2

# 补充

Arrays.binarySearch 的工作方式：

  1. 如果数组中存在目标值：
    • 返回目标值的索引（ i >= 0 ）。
  2. 如果数组中不存在目标值：
    • 返回插入点的负数减一（即 -(插入点) - 1 ）。
    • 这个 “插入点” 是指目标值在数组中保持排序的位置。

2024-12-17

# 更多的例题

题目 2300
咋一眼没看出来可以用二分
二分的应用条件：

  1. 有序（sort（Array））
  2. 有 >= 的条件，或者等价的条件

这道题目是 xy > value 的形式，可以转化为 y > value/x，接着使用二分来解决
！[[Pasted image 20241217234041.png]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        for (int i = 0; i < spells.length; i++) {
            long target = (success - 1) / spells[i];
            if (target < potions[potions.length - 1]) { // 防止 long 转成 int 溢出
                spells[i] = potions.length - upperBound(potions, (int) target);
            } else {
                spells[i] = 0;
            }
        }
        return spells;
    }

    // 直接二分 long 是 28ms，改成 int 是 26ms
    private int upperBound(int[] nums, int target) {
        int left = -1, right = nums.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] <= target
            // nums[right] > target
            int mid = (left + right) >>> 1;
            if (nums[mid] > target) {
                right = mid; // 二分范围缩小到 (left, mid)
            } else {
                left = mid; // 二分范围缩小到 (mid, right)
            }
        }
        return right;
    }
}