算法及数据结构系列 - 二分查找

发布于:2025-03-18 ⋅ 阅读:(25) ⋅ 点赞:(0)

系列文章目录

算法及数据结构系列 - BFS算法


二分查找

框架思路

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

计算 mid 时需要防止溢出,代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同,但是有效防止了 left 和 right 太大直接相加导致溢出。

经典题型

二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

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

寻找左侧边界

注意: 当 val 不存在时,得到的索引恰好是比 val 大的最小元素索引

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

寻找右侧边界

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

刷题

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

提示: 吃每一堆分别要几小时;寻找左侧边界

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        Arrays.sort(piles);
        int left = 1, right = piles[piles.length - 1] + 1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(canFinish(mid, piles, H)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean canFinish(int k, int[] piles, int H){
        long tmpHour = 0;
        for(int i = 0; i< piles.length;i++){
            tmpHour += (long)(piles[i] / k);
            if(piles[i] % k > 0){
                tmpHour ++;
            }
        }
        if(tmpHour <= H){
            return true;
        }else{
            return false;
        }
    }
}

1011. 在 D 天内送达包裹的能力

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例:

输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出:15
解释:
船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
第 1 天:1, 2, 3, 4, 5
第 2 天:6, 7
第 3 天:8
第 4 天:9
第 5 天:10

请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 s
class Solution {
    public int shipWithinDays(int[] weights, int D) {
        if(weights.length == 0){
            return 0;
        }
        int len = weights.length;
        int left = weights[0], right = (weights[0] + weights[len -1]) * len / 2 + 1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(canFinish(weights, D, mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;

    }

    public boolean canFinish(int[] w, int D, int cap){
        int i = 0;
        for (int day = 0; day < D; day++) {
            int maxCap = cap;
            while ((maxCap -= w[i]) >= 0) {
                i++;
                if (i == w.length)
                    return true;
            }
        }
        return false;
    }
}

392. 判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int fromIndex = 0;
        for(int i = 0; i < s.length(); i++){
            char tmp = s.charAt(i);
            int j = fromIndex;
            for(; j < t.length(); j++){
                if(t.charAt(j) == tmp){
                    fromIndex = j + 1;
                    break;
                }
            }
            if(j == t.length()){
                return false;
            }
        }
        return true;
    }
}

后续挑战 :

如果有大量输入的 S,称作S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        ArrayList<Integer>[] index = new ArrayList[256];
        // 先记下 t 中每个字符出现的位置
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            if (index[c] == null) 
                index[c] = new ArrayList<>();
            index[c].add(i);
        }
        int j = 0; // t 上的指针
        // 借助 index 查找 s[i]
        for (int i = 0; i < m; i++) {
            char c = s.charAt(i);
            // 整个 t 压根儿没有字符 c
            if (index[c] == null) return false;
            int pos = find(index[c], j);
            // 二分搜索区间中没有找到字符 c
            if (pos == index[c].size()) return false;
            // 向前移动指针 j
            j = index[c].get(pos) + 1;
        }
        return true;
    }

    public int find(ArrayList<Integer> arr, int target){
        int left = 0, right = arr.size();
        while(left < right){
            int mid = left + (right - left)/2;
            if(arr.get(mid) == target){
                right = mid;
            }else if (arr.get(mid) > target){
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
}

网站公告

今日签到

点亮在社区的每一天
去签到