首页 > 其他分享 >二分查找

二分查找

时间：2024-04-29 23:35:52浏览次数：25  
标签：二分 cnt return int mid 查找 import public

1.0 二分查找概念

key words： 单调区间、最大化最小值（最小化最大值）、时间复杂度O（logn）

 1.1 二分模板

模板来自于 AK机大厂笔试 星球。

1.1.1 在非递减数组中找到第一个 ≥ x的数

public int lowerBound(int[] nums, int x) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l+(r-l)>>1;
        if (nums[mid] >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (nums[l] < x) {
        return -1;
    } else {
        return l;
    }
}

1.1.2 在非递减数组中找到第一个>x的数

public int upperBound(int[] nums, int x) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l+(r-l)>>1;
        if (nums[mid] > x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (nums[l] > x) {
        return l;
    } else {
        return -1;
    }
}

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

找到第一个等于target下标l

找到第一个大于target下标l1

返回 (l,l1)

package com.coedes.binary_search.likou34;

/**
 * @description：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=list&envId=yhAjDBEG
 * @author： wenLiu
 * @create： 2024/4/22 14:00
 */
public class Solution {

    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return new int[]{-1, -1};
        int l = 0, r = n - 1;
        //找到第一个target值 （binarysearch >= target）
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return new int[]{-1, -1};
        } else {
            //找到第一个大于target 下标
            int l1 = 0, r1 = n - 1;
            while (l1 < r1) {
                int mid = (l1 + r1) / 2;
                if (nums[mid] > target) {
                    r1 = mid;
                } else {
                    l1 = mid + 1;
                }
            }
            if (nums[l1]==target) {
                return new int[]{l, l1};
            }else {
                return new int[]{l, l1 - 1};
            }
        }
    }
}

　　

 1.2 二分答案

 1.2.1 二分答案模板

 ① 最大值最小化（还有叫最小化最大值的...注意理解就是求最大值里面最小的那个....题目求的是一个最小值）

import java.util.*;

public class Main {
    // 判断当前枚举的答案x是否合法
    static boolean check(int x) {
        // 在这里实现具体的判断逻辑
        return true;
    }

    public static void main(String[] args) {
        int l = 0, r = (int)1e9;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        // 最后的答案是l
        System.out.println(l);
    }
}

　　

②最小值最大化（求的是一个最大值）

import java.util.*;

public class Main {
    // 判断当前枚举的答案x是否合法
    static boolean check(int x) {
        // 在这里实现具体的判断逻辑
        return true;
    }

    public static void main(String[] args) {
        int l = 0, r = (int)1e9;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        // 最后的答案是l
        System.out.println(l);
    }
}

 

2023美团-分糖果

将两种不同口味的糖果（a 个和 b 个）分给 n 个人。

确保每块糖果都被分配。

每个人只能得到一种糖果。

考虑如何分配这些糖果以使得分得最少糖果的人获得尽可能多的糖果。

输入描述

第一行一个正整数 T ，表示有 T 组数据。

对于每一组数据，输入一行n，a，b，中间用空格隔开。

1<a,b<10000，2≤n≤a+b，1≤T≤100

输出描述

对于每一组数据，输出仅一行一个整数，表示答案。

in:
2
5 2 3
4 7 10
out:
1
3

 

题解：二分答案+check
  • “考虑如何分配这些糖果以使得分得最少糖果的人获得尽可能多的糖果。”  =>  这是一道最小化最大值题目 => mid = (l+r+1)>>1
  • 题目问“如何分配这些糖果” => 设 每个人分 x 个 。

　　　　=> x 定义域？ =>  n ≤ a+b => 当 n = a+b =>  x ≥ 1 

　　　　=> x ≤（a+b）/ n  

　　　　=> x ∈ [1,(a+b)/n] 

  •  因为“每个人只能得到一种糖果” => ( a/x + b/x ) >= n
  •  单调性证明：f(x) = a/x + b/x  , 分给单孩子糖果越多 x，则分到糖果孩子数量就越少 f(x)  ,f(x)是个单调递减函数，可以使用二分。
  • 总的来说，问题最后转化为： x ∈ [1,(a+b)/n] ，枚举x找到满足( a/x + b/x ) >= n条件下x的最值。
package com.coedes.binary_search.meituan20230415;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @description：https://xuq7bkgch1.feishu.cn/docx/CAbedNJ5KobvinxdyKgcKsrlnrd
 * @author： wenLiu
 * @create： 2024/4/22 15:22
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        for (int i = 0; i < T; i++) {
            String[] s = reader.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int a = Integer.parseInt(s[1]);
            int b = Integer.parseInt(s[2]);
            System.out.println(helper(n, a, b));
        }
    }

    private static int helper(int n, int a, int b) {
        int l = 1, r = (a + b) / 2;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(a, b, mid, n)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l ;
    }

    private static boolean check(int a, int b, int x, int n) {
        return (a / x + b / x) >= n;
    }
}

2023.08.26-美团-第一题

给定一个整数z，now从0开始，你有两种操作:

1.now += x

2.now += y

限定条件:

每天可以操作1次操作1，操作2使用完后必须过至少2天才能再次使用。

问最少天数使得now ≥ z 。

输入描述
第一行三个整数 x , y , z <= 1e9
输出描述
一个整数，输出最少次数。

in:1 2 10
out:6

 

模拟：

package com.coedes.binary_search.meituan20230826;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @description：https://codefun2000.com/p/P1493
 * @author： wenLiu
 * @create： 2024/4/22 19:10
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        long x = Long.parseLong(s[0]);
        long y = Long.parseLong(s[1]);
        long z = Long.parseLong(s[2]);
        int cnt = 2;
        long now = 0;
        long res = 0;
        while (now < z) {
            if (cnt == 2) {
                now += (x + y);
                cnt = 0;
            } else {
                cnt++;
                now += x;
            }
            res++;
        }
        System.out.println(res);
    }
}

 

可以发现  now 是以 3 * x + y为一组进行变化...

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x, y, z;
        
        // 输入 x、y、z 的值
        x = scanner.nextInt();
        y = scanner.nextInt();
        z = scanner.nextInt();

        // 计算余数
        int rest = z % (3 * x + y);
        
        // 根据不同的余数情况进行计算和输出
        if (rest == 0) {
            System.out.println((z / (3 * x + y)) * 3);
        } else {
            if (rest <= x + y) {// 一天能够完成
                System.out.println((z / (3 * x + y)) * 3 + 1);
            } else if (rest <= 2 * x + y) {// 两天能够完成
                System.out.println((z / (3 * x + y)) * 3 + 2);
            } else {// 三天能够完成
                System.out.println((z / (3 * x + y)) * 3 + 3);
            }
        }

        scanner.close();
    }
}

　　

 

2023.04.12-实习笔试-第一题-购物系统的降级策略

  • 　　问题背景：
    • 　　N 个客户端通过发送请求（表示为 R=[R1, R2, ..., RN]）与核心购物系统进行通信。
    • 　　核心购物系统有最大调用量限制 cnt。

  • 降级规则：

    • 　　如果所有客户端请求总和 sum(R1, R2, ..., RN) 小于 cnt，则返回 -1。
    • 　　如果请求总和超过 cnt，需设定一个阈值 valu。
    • 　　对于超过 value 的单个客户端的请求量，必须限制为 value，而其他未达到 value 的客户端请求可以正常发起。

  • 问题目标：

    • 　　求出最大的 value（value 可以为0）。
    • 　　保证客户端请求总量不超过核心购物系统的最大调用量 cnt。
    • 　　value 要尽可能大，以确保交易顺利进行。

输入描述
第一行:每个客户端的调用量(整型数组)

第二行:核心购物系统的最大调用量
0< R.length ≤ 105,0 ≤  R[i] ≤ 105 ,0 ≤ cnt ≤ 109

输出描述
调用量的阈值 value

in1:
1 4 2 5 5 1 6 
13
out1:
2

样例解释

因为 1+4+2+5+5+1+6>131+4+2+5+5+1+6>13 ，将  value 设置为 22 ，则 1+2+2+2+2+1+2=12<131+2+2+2+2+1+2=12<13 。所以  value 为 22 。

in2：

1 7 8 8 1 0 2 4 9
7

out2：

0

样例解释

因为即使  value 设置为 11 , 1+1+1+1+1+1+1+1=8>71+1+1+1+1+1+1+1=8>7 也不满足，所以 value 只能为 0 

 

思路：

根据题目“要求求出最大的  value（value 可以为0）”  => 很明显自变量为 value ，其下界为0。 上界我开始认为是cnt,后面想了想，既然已知请求序列，那么最大值可以缩小为max(Ri) 。

所以 value ∈ [0,max(Ri)] , 设f(value)为进入核心购物模块请求数量，则 f(value) = sum（min(Ri,value)）&& f(value) <= cnt; 显然value越小f（value）越大 ,函数单调，可以考虑二分结果。

题目为最小化求最大值，采用模板②，mid = (l+r+1)>>1 ，l = 0 , r = max(Ri) 

package com.coedes.binary_search.huawei20230412;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Map;

/**
 * @description：https://codefun2000.com/p/P1189
 * @author： wenLiu
 * @create： 2024/4/22 19:34
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strOfR = reader.readLine().split(" ");
        int n = strOfR.length;
        int[] R = new int[n];
        for (int i = 0; i < n; i++) {
            R[i] = Integer.parseInt(strOfR[i]);
        }
        long cnt = Long.parseLong(reader.readLine());
        int maxRi = Arrays.stream(R).max().getAsInt();
        int l = 0, r = maxRi;//O(logn)
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid, cnt, R)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (r == maxRi) {
            System.out.println(-1);
        } else {
            System.out.println(r);
        }
    }

    private static boolean check(int mid, long cnt, int[] R) {
        long sum = 0;
        int n = R.length;
        for (int i = 0; i < n; i++) {
            sum += Math.min(mid, R[i]);
            if (sum > cnt) {
                return false;
            }
        }
        return true;
    }
}

　　

 

2023腾讯音乐-划分字符串

描述

有一个算法可以将外部声音转录为只包含小写字母的字符串 s，并计算该字符串的权值 w(s)，定义为 s 的长度乘以 s 中不同字母的个数。

例如，对于字符串 s = "abacb"，其权值为 w("abacb") = 5 * 3 = 15。

接着，算法将字符串 s 切分为 k 个连续的子串 s1, s2, …, sk，以使这 k 个子串中权值最大的子串的权值尽可能小（其中 1 <= k <= s.length<= 500000）。

你需要输出切分后权值最大的子串的权值。

input：
adadasda
3

output：
8

 

思路：

“k 个子串中权值最大的子串的权值尽可能小” =>“输出切分后权值最大的子串的权值” => 小的里面找最大的=>  最大化最小值...

题目要求的是最大的子串权值，设其为x.

x ∈ [1,500000*26]

1. 使用二分查找确定最大子串权值 `x` 的最小可能取值。
2. 在二分查找中，通过调用 `check` 方法判断当前尝试的最大子串权值 `mid` 是否满足条件。
3. `check` 方法用于判断给定最大子串权值 `x` 是否能划分出不超过 `k` 个连续子串：
- 遍历字符串 `s`，维护当前子串的字符集合 `st` 和长度 `len`。
- 当子串权值超过 `x` 时，表示当前子串结束，增加子串计数。
4. 根据 `check` 方法的结果，调整二分查找的边界。
5. 最终输出满足条件的最小化最大值，即最大子串权值的最小可能取值。

这个算法通过简单描述了二分查找和子串划分的思路，用于解决最小化最大值问题。

 

package com.coedes.binary_search.txmusic20230323;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

/**
 * @description：https://xuq7bkgch1.feishu.cn/docx/CAbedNJ5KobvinxdyKgcKsrlnrd
 * @author： wenLiu
 * @create： 2024/4/25 18:04
 */


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int k = Integer.parseInt(reader.readLine());
        int n = s.length();

        int l = 1;
        int r = 26*500000;

        while (l < r) {
            int mid = (l + r) / 2;
            if (check(s, k, mid, n)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        System.out.println(l);
    }

    private static boolean check(String s, int k, int x, int n) {
        int cnt = 0;
        int len = 0;
        Set<Character> st = new HashSet<>();

        for (int i = 0; i < n; i++) {
            st.add(s.charAt(i));
            len++;
            if (st.size() * len > x) {
                cnt++;
                st.clear();
                len = 0;
                i--;
            }
        }

        if (!st.isEmpty()) {
            cnt++;
        }

        return cnt <= k;
    }
}

LeetCode 1552. 两球之间的磁力

    1. 理解问题： 给定球的位置数组 position 和篮子数量 m，要求将这些球放入篮子中，使得任意两球间的最小磁力尽可能大。最小磁力指任意两球之间的距离，要使这个最小磁力最大化。

    2. 问题转化： 我们需要找到一个最大的最小磁力 x，使得能够将 m 个球放入篮子中，并且满足任意两球之间的距离至少为 x。我们可以通过二分搜索来确定这个 x 的值。

    3. 二分搜索算法：

      • 首先对 position 数组进行排序，以便更方便地计算任意两球之间的距离。
      • 设定二分搜索的范围。最小值 left 可以设为 1，最大值 right 则可以设为 position[position.length - 1] - position[0]，即位置数组的最大距离。
      • 在二分搜索的过程中，对于每个中间值 mid，判断是否可以将 m 个球放入篮子中，使得任意两球之间的距离至少为 mid。
        • 使用贪心的方法来模拟放球的过程：从第一个球开始，依次尝试将球放入位置，并确保每次放球的位置与上一个球的位置之间的距离不小于 mid。
        • 如果可以放下所有球，说明当前 mid 值满足条件，将 left 向右移动；否则，将 right 向左移动。

    4. 具体步骤：

      • 对 position 数组进行排序。
      • 使用二分搜索确定最大的满足条件的 x 值。
      • 在每个二分步骤中，使用贪心算法检查当前 mid 值是否可以满足将 m 个球放入篮子中的条件
package com.coedes.binary_search.likou1552;

import java.util.Arrays;

/**
 * @description：https://leetcode.cn/problems/magnetic-force-between-two-balls/
 * @author： wenLiu
 * @create： 2024/4/25 21:16
 */
public class Solution {
    public int maxDistance(int[] position, int m) {
        //使得任意两球间 最小磁力 最大 =>最大化最小值 => 最小值最大化 => 求mid最大值
        Arrays.sort(position);
        int l = 1;
        int r = position[position.length - 1] - position[0];
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid, m, position)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private boolean check(int mid, int m, int[] position) {
        int cnt = 0;
        int pre = position[0];//排序后第一个位置一定要放球（贪心）假设有3个篮子2个球 如果第一个篮子不放球那么2球间距离就不是最大值了
        cnt++;
        for (int i = 1; i < position.length; i++) {
            if (position[i] - pre >= mid) {//position排序后几不用abs(position[i]-pre)
                pre = position[i];
                cnt++;
            }
        }
        return cnt >= m;
    }
}

LeetCode 878. 第 N 个神奇数字

 思路：二分+lcm(gcd)

设 f(x)表示为小于等于 x &lt;span class="katex"&gt;&lt;span class="katex-mathml"&gt;&lt;span class="katex-html"&gt;&lt;span class="base"&gt;&lt;span class="strut"&gt;&lt;span class="mord mathnormal"&gt;的「神奇数字」个数个数 ， 那么 f（x）等于从1到x能被a整除个数+能被b整除的个数-既能被a整除又能被b整除个数（a,b最小公倍数）

  • f(x)=⌊x/a​⌋+⌊x/b​⌋−⌊x/c​⌋
  • c = lcm(a,b) = a*b/gcd(a,b) = a/gcd(a,b)*b (防止int溢出先除后乘)

用较大的数除以较小的数，得到余数。

将较小的数和余数作为新的两个数，重复步骤1，

直到余数为0余数为0时的除数即为两数的最大公约数。

　　 int gcd(int x,int y){

　　　　return y==0?x:gcd(y,x%y)　;　

　　}

超时了...

package com.coedes.binary_search.likou878;

/**
 * @description：https://leetcode.cn/problems/nth-magical-number/description/?envType=list&envId=yhAjDBEG
 * @author： wenLiu
 * @create： 2024/4/25 23:07
 */
public class Solution {
    static final int mod = (int) (10E9 + 7);

    public int nthMagicalNumber(int n, int a, int b) {
        int l = 1, r = (int) 10E9;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(a, b, mid) >= n) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r % mod;
    }

    private int check(int a, int b, int mid) {
        return mid / a + mid / b - mid / lcm(a, b);
    }

    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

　

参考大佬优化的上界r 灵茶山艾府  当 x= min(a,b)·n时,至少就有 n 个神奇数字了因此可以取它为二分上界，注意还要开long，因为n达到了 10e9...

 

 

LeetCode 1482. 制作 m 束花所需的最少天数

 

思路：二分答案+双指针

 

题目问：请你返回从花园中摘 m 束花需要等待的最少的天数。 那就设 摘 m 束花需要等待的最少的天数为 x 天。
m(x) 为 摘 m 束花与等待天数x函数 ， 显然m(x) 随着 x 递增而递增... 考虑二分答案

最少的天数 => 找最小值 => mid = l + (r-1)>>1;

check函数用来判断

 

标签：二分,cnt,return,int,mid,查找,import,public
From： https://www.cnblogs.com/alohablogs/p/18150433

相关文章

  • BST二叉查找树的接口设计
    /***********************************************************************************************************设计BST二叉查找树的接口，为了方便对二叉树进行节点的增删，所以采用双向不循环链表实现，每个节点内部都需要*有2个指针，分别指向该节点的左子树(lchild)和右子树......
  • 二分查找的左闭右开和左闭右闭写法
    0.参考参考链接:二分查找的左闭右开和左闭右闭写法1.思路0.序言lower_bound查找的是升序序列中的第一个出现target的pos，区间应从右向左收缩。upper_bound查找的是升序序列中的最后一个出现target的pos，区间应从左向右收缩。主循环判断本质目的是为了确保整个区间能够被检索......
  • 2015 ACM ICPC Singapore Regional D（折半枚举+二分）
    D-AssociationofComputerMaintenance题意给定至多350个小于100的质数，对于所有质数之积k将它分解为两个数a和b使得a*b=k。输出最小的a+b，并对1e9+7取模分析首先考虑想如果想让a+b最小，即让abs(a-b)最小。随后根据限制条件k的因子数不超过1e10，容易想到将k拆分成k1和k2，此......
  • P5896 [IOI2016] aliens （斜率优化 dp+wqs 二分）
    我们可以把所有点都对称到主对角线下方。然后每个点如果想被覆盖都会有一个最小的三角形，我们可以贪心的只留必须选的点。如果把剩下的点按\(x\)坐标升序排序，可以发现他们的\(y\)坐标也是升序排序的。记剩余点个数为\(n\)，显然每个点都选自己的最小三角形最好。但是有可能\(......
  • 查找datafocus安装路径
    1.cat/etc/profile|grepDATA   2.解读下面一行master-192-168-0-15:/df-share表示该文件系统是通过网络文件系统(NFS)挂载的，其位置为master-192-168-0-15主机上的/df-share目录实际上，在主机上并没有名为/df-share的目录，这是一个挂载点的名称，而不是实际的目......
  • 查找链表倒数第k个数位置上的结点
    （1）描述算法的基本思想由题可知，该链表是个单向链表，如果要找到倒数第k个值，我们必须找到该链表的尾部，而单向链表从尾部向头部找倒数第k个值比较麻烦，所以我们可以从头部去找倒数第k个值（2）描述算法的详细实现步骤我们可以利用两个指针去遍历该链表，一个指针遍历完该链表计算出结点个数......
  • 如何用Sublime Text实现正则查找与替换
    比如将下面的汉字语义加上中括号[{"text":"微笑","path":"emot01.png"},{"text":"大笑","path":"emot02.png"},{"text":"鼓掌","......
  • [python省时间]处理文档，包括批量查找，替换，
    1、批量查找替换#-*-coding:utf-8-*-importosimportre#path=os.getcwd()str_old='insert'str_new='frs.event.queue'file_formate='init.sql'file_sql=open(r'F:\bak\init_all.sql','r+',encoding=......
  • 【基础】整体二分
    namespaceMultiBinarySearch{staticconstintMAX_QUERY=2e5+10;structQuery{intid,cnt;//分cnt组时，每组的大小最大有多大？容易知道分的组数越多，其最大的siz会变小。};intans[MAX_QUERY];intcheck(intM){intcnt=0;//实现这个根据......
  • 说说你对二分查找的理解？如何实现？应用场景？
     一、是什么在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法想要应用二分查找法，则这一堆数应有如下特性：存储在数组中有序排序搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束如果某一特定元素大......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99