【秋招刷题打卡】Day02-二分系列之-二分查找

2024-06-22 20:36

本文主要是介绍【秋招刷题打卡】Day02-二分系列之-二分查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Day02-二分系列之-二分查找

前言

给大家推荐一下咱们的 陪伴打卡小屋 知识星球啦,详细介绍 =>笔试刷题陪伴小屋-打卡赢价值丰厚奖励 <=

⏰小屋将在每日上午发放打卡题目,包括:

  • 一道该算法的模版题 (主要以力扣,牛客,acwing等其他OJ网站的题目作为模版)
  • 一道该算法的应用题(主要以往期互联网大厂 笔试真题 的形式出现,评测在咱们的 笔试突围OJ

在这里插入图片描述

小屋day02

我们预计花三天的时间来介绍和巩固二分的题目,其中包括

  • 二分查找
  • 二分答案
  • 二分最大化最小值/最小化最大值

其中笔试常考的为后两类,今年春招中出现了不下 10 次。

引言

举个二分的例子

比如有一个有序单调不减的数组 a r r arr arr,以及一个目标值 X X X ,要求在 a r r arr arr 中找到第一个 ≥ X \ge X X 的数。

做法:每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中间元素大于所查找的值同理,只需到左侧查找。

通过二分搜索能够有效的帮原本 O ( n ) O(n) O(n) 遍历数组的时间复杂度降为 O log ⁡ ( n ) O \log(n) Olog(n)

当然二分能做的事远远不止如此,一个题目,如果一个区间具有单调性质,那么一定可以二分,但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分,二分的题目,往往会出现最大值最小值, 或者单调性质。题目如果出现最大的最小值最小的最大值的类似的字眼,一般是可以使用二分来解决。

✨ 以下提供一个,本人长期使用的一个比较好用的手写二分模版

二分模版

二分模板一共有两个,分别适用于不同情况,使用时只需修改check函数即可。
算法思路:假设目标值在闭区间 [l, r] 中, 每次将区间长度缩小一半,当 l = r 时,我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid][mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加 1。

  • CPP

    int bsearch_1(int l, int r)
    {// l 为左端点,r 为右端点,都是闭区间// 使用时只需修改check函数即可while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; // check函数代表你需要进行的判断操作// 最终的答案会满足check条件else l = mid + 1; // 一定是这么写 不用多想}return l; // 此时的 l 为答案 (l == r)
    }
    
  • Java

    public int bsearch_1(int l, int r) {// l 为左端点,r 为右端点,都是闭区间// 使用时只需修改check函数即可while (l < r) {int mid = (l + r) >> 1;if (check(mid)) {r = mid; // check函数代表你需要进行的判断操作// 最终的答案会满足check条件} else {l = mid + 1; // 一定是这么写 不用多想}}return l; // 此时的 l 为答案 (l == r)
    }
    
  • Python

    def bsearch_1(l, r):# l 为左端点,r 为右端点,都是闭区间# 使用时只需修改check函数即可while l < r:mid = (l + r) // 2if check(mid):r = mid # check函数代表你需要进行的判断操作# 最终的答案会满足check条件else:l = mid + 1 # 一定是这么写 不用多想return l # 此时的 l 为答案 (l == r)
    
版本2

当我们将区间[l, r]划分成[l, mid - 1][mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。

  • CPP

    int bsearch_2(int l, int r)
    {// l 为左端点,r 为右端点,都是闭区间// 使用时只需修改check函数即可while (l < r){int mid = l + r + 1 >> 1; // 注意这里要多加 1if (check(mid)) l = mid; // check函数代表你需要进行的判断操作// 最终的答案会满足check条件else r = mid - 1; // 一定是这么写 不用多想}return l; // 此时的 l 为答案 (l == r)
    }
    
  • Java

    public int bsearch_2(int l, int r) {// l 为左端点,r 为右端点,都是闭区间// 使用时只需修改check函数即可while (l < r) {int mid = (l + r + 1) >> 1;// 注意这里要多加 1if (check(mid)) {l = mid; // check函数代表你需要进行的判断操作// 最终的答案会满足check条件} else {r = mid - 1; // 一定是这么写 不用多想}}return l; // 此时的 l 为答案 (l == r)
    }
    
  • Python

    def bsearch_2(l, r):# l 为左端点,r 为右端点,都是闭区间# 使用时只需修改check函数即可while l < r:mid = (l + r + 1) // 2 # 注意这里要多加 1if check(mid):l = mid # check函数代表你需要进行的判断操作# 最终的答案会满足check条件else:r = mid - 1 # 一定是这么写 不用多想return l # 此时的 l 为答案 (l == r)
    
什么时候使用版本1 or 2?

清隆这边给大家总结了一下:

  • 如果在 if(check()) 判断之后需要 跟新(左移) 右端点的,用 版本1
  • 反之,如果是需要 跟新(右移) 左端点的,用 版本2

接来下我们看看模版如何运用

🎀 模版题

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

题目链接🔗:https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)

题目描述

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。


解题思路

对于左端点我们二分找到第一个 >= target 的下标,记为 left,如果没有则为 -1

对于右端点我们二分找到最后一个 <= target 的下标,记为 right,如果没有则为 -1

最终的答案为 [left, right]

参考代码

  • Python

    class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def bsearch_1(l, r): # 找到第一个 >= target的位置def check(index):if nums[index] >= target:return True # 说明当前 nums[mid] 太大了,答案下标应该在 <= index ,所以返回 True 缩小右端点return False# l 为左端点,r 为右端点,都是闭区间# 使用时只需修改check函数即可while l < r:mid = (l + r) // 2if check(mid):r = mid # check函数代表你需要进行的判断操作# 最终的答案会满足check条件else:l = mid + 1 # 一定是这么写 不用多想if l >= n or nums[l] != target: # 代表没有找到答案return -1return l # 此时的 l 为答案 (l == r)def bsearch_2(l, r): # 找到最后一个 <= target的位置def check(index):if nums[index] <= target: # 说明当前 nums[mid] 太小了,答案下标应该 >= index, 所以返回 True 缩小左端点return Truereturn False# l 为左端点,r 为右端点,都是闭区间# 使用时只需修改check函数即可while l < r:mid = (l + r + 1) // 2 # 注意这里要多加 1if check(mid):l = mid # check函数代表你需要进行的判断操作# 最终的答案会满足check条件else:r = mid - 1 # 一定是这么写 不用多想if l >= n or nums[l] != target: # 代表没有找到答案return -1return l # 此时的 l 为答案 (l == r)n = len(nums)left = bsearch_1(0, n - 1)# 找到左端点,即第一个 >= target 的位置right = bsearch_2(0, n - 1) # 找到右端点,即最后一个 <= target 的位置return [left, right]
    
  • Java

    class Solution {public int[] searchRange(int[] nums, int target) {int n = nums.length;int left = bsearch_1(nums, target, 0, n - 1);  // 找到左端点,即第一个 >= target 的位置int right = bsearch_2(nums, target, 0, n - 1); // 找到右端点,即最后一个 <= target 的位置return new int[]{left, right};}private int bsearch_1(int[] nums, int target, int l, int r) {while (l < r) {int mid = (l + r) / 2;if (nums[mid] >= target) {r = mid; // 说明当前 nums[mid] 太大了,答案下标应该在 <= index ,所以返回 True 缩小右端点} else {l = mid + 1; // 一定是这么写 不用多想}}if (l >= nums.length || nums[l] != target) {return -1; // 代表没有找到答案}return l; // 此时的 l 为答案 (l == r)}private int bsearch_2(int[] nums, int target, int l, int r) {
  • Cpp

    class Solution {
    public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();int left = bsearch_1(nums, target, 0, n - 1);  // 找到左端点,即第一个 >= target 的位置int right = bsearch_2(nums, target, 0, n - 1); // 找到右端点,即最后一个 <= target 的位置return {left, right};}private:int bsearch_1(vector<int>& nums, int target, int l, int r) {// l 为左端点,r 为右端点,都是闭区间while (l < r) {int mid = (l + r) / 2;if (check1(nums, mid, target)) {r = mid; // check函数代表你需要进行的判断操作// 最终的答案会满足check条件} else {l = mid + 1; // 一定是这么写 不用多想}}if (l >= nums.size() || nums[l] != target) {return -1; // 代表没有找到答案}return l; // 此时的 l 为答案 (l == r)}bool check1(vector<int>& nums, int index, int target) {if (nums[index] >= target) {return true; // 说明当前 nums[mid] 太大了,答案下标应该在 <= index ,所以返回 True 缩小右端点}return false;}int bsearch_2(vector<int>& nums, int target, int l, int r) {// l 为左端点,r 为右端点,都是闭区间while (l < r) {int mid = (l + r + 1) / 2; // 注意这里要多加 1if (check2(nums, mid, target)) {l = mid; // check函数代表你需要进行的判断操作// 最终的答案会满足check条件} else {r = mid - 1; // 一定是这么写 不用多想}}if (l >= nums.size() || nums[l] != target) {return -1; // 代表没有找到答案}return l; // 此时的 l 为答案 (l == r)}bool check2(vector<int>& nums, int index, int target) {if (nums[index] <= target) {return true; // 说明当前 nums[mid] 太小了,答案下标应该 >= index, 所以返回 True 缩小左端点}return false;}
    };

🍰 笔试真题

  • 直接考察二分查找位置的笔试题目并不多,更多是和其他算法相结合

  • 该题来自今年 阿里系春招 的笔试题,本题为最后一题,题目难度为中等偏上,其中涉及到了 质数筛 的数论知识,大家如果对这方面不熟悉可以先去了解一下,咱们后面开始数论篇的时候会详细讲解

  • 如果有困难的小伙伴这边可以根据参考代码 只写二分 的部分,本篇主目的是对二分查找进行介绍,可以等后续数论篇的时候再来补这里的 **质数筛 **部分~。

神奇数字

🔗评测链接:https://app5938.acapp.acwing.com.cn/contest/3/problem/Day02

题目描述

LYA 定义了一个神奇数字 n u m num num,其要满足 n u m = a 2 + b 3 + c 4 num = a^2 + b^3 + c^4 num=a2+b3+c4,其中 a , b , c a,b,c a,b,c 都为质数。于是 LYA 想知道在 1 ∼ n 1 \sim n 1n 中有多少个这样的神奇数字呢,请你告诉 LYA。

输入格式

第一行为 t t t,表示有 t t t 组数据。

接下来有 t t t 行,每行为一个整数 n n n

输出格式

输出为 t t t 行,每行为一组答案。

样例输入

3
28
33
47

样例输出

1
2
3

数据范围

  • 1 < t < 1 0 5 1 < t < 10^5 1<t<105
  • 1 ≤ n < 1 0 6 1 \leq n < 10^6 1n<106

题解

本题可以使用预处理 + 二分查找的方法来解决。

首先,预处理出所有可能的神奇数字。由于 a , b , c a,b,c a,b,c 都是质数,我们可以先用埃氏筛法筛选出 1 ∼ 1 0 6 1 \sim 10^6 1106 内的所有质数,存入数组 p r i m e prime prime 中。

然后,我们使用三重循环枚举所有可能的 a , b , c a,b,c a,b,c,计算出对应的神奇数字 v a l val val,并将其加入到集合 s s s 中。注意,为了避免重复计算,我们需要保证 a 2 + b 3 + c 4 < 1 0 6 a^2 + b^3 + c^4 < 10^6 a2+b3+c4<106,虽然有三重循环,但有大量剪枝,总计算次数在 3 × 1 0 5 3 \times 10 ^ 5 3×105 左右。

接下来,将集合 s s s 中的元素转移到数组 v v v 中,并对 v v v 进行排序。

最后,对于每个询问 n n n,我们使用二分查找在数组 v v v 中查找不超过 n n n 的元素个数,即为答案。

时间复杂度 O ( t log ⁡ n ) O(t \log n) O(tlogn),空间复杂度 O ( n ) O(n) O(n)

参考代码
  • Python
import sys
input = lambda: sys.stdin.readline().strip()
import bisectprime = []
N = 10 ** 6 + 1
st = [False] * Nfor i in range(2, N):if not st[i]:prime.append(i)for j in range(i, N, i):st[j] = True v = []
s = set()
n = len(prime)for a in prime:if a * a >= N:breakfor b in prime:if a * a + b ** 3 >= N:breakfor c in prime:val = a ** 2 + b ** 3 + c ** 4if val >= N:breaks.add(val)v = sorted(s)
# 将右边界跟新成一个比较大的数
v.append(10**9)
m = len(v)
t = int(input())
# ----- 以下为二分的部分 -----
for _ in range(t):x = int(input())# 找到 v 中不超过 x 的个数# 这里采用二分的第一种模版,找到 v 中第一个 > x 的下标# 也可以采用第二个模版,找到 v 中最后一个 <= x 的下标# 1.手写二分l, r = 0, m - 1while l < r:mid = (l + r) // 2if v[mid] > x:r = midelse:l = mid + 1print(l)# 2. 也可以用库函数实现# idx = bisect.bisect_right(v, x) # 库函数 返回 v 中第一个大于 x 的下标# print(idx)
  • Java
import java.util.*;public class Main {public static void main(String[] args) {int N = 1000001;boolean[] st = new boolean[N];List<Integer> prime = new ArrayList<>();for (int i = 2; i < N; i++) {if (!st[i]) prime.add(i);for (int j = i; j < N; j += i) st[j] = true;}Set<Long> s = new HashSet<>();int n = prime.size();for (int a : prime) {if ((long) a * a >= N) break;for (int b : prime) {if ((long) a * a + (long) b * b * b >= N) break;for (int c : prime) {long val = (long) a * a + (long) b * b * b + (long) c * c * c * c;if (val >= N) break;s.add(val);}}}List<Long> v = new ArrayList<>(s);Collections.sort(v);// 将右边界跟新成一个比较大的数,方便维护long maxv_right = 1000_000_000;v.add(maxv_right);Scanner scanner = new Scanner(System.in);int t = scanner.nextInt();int m = v.size();// ----- 以下为二分的部分 -----while (t-- > 0) {int x = scanner.nextInt();// 需要在 v 中找到 所有 <= x 的个数// 这里采用二分的第一种模版,找到 v 中第一个 > x 的下标// 也可以采用第二个模版,找到 v 中最后一个 <= x 的下标int L = 0, R = m;while(L < R){int mid = L + R >> 1;if(v.get(mid) > x) R = mid; elseL = mid + 1;}System.out.println(L);}}
}
  • Cpp
#include <bits/stdc++.h>using namespace std;
using ll = long long;const int N = 1e6 + 1;
bool st[N];
vector<int> prime;int main() {for (int i = 2; i < N; i++) {if (!st[i]) prime.push_back(i);for (int j = i; j < N; j += i) st[j] = true;}unordered_set<int> s;int n = prime.size();for (auto a : prime) {if (1ll * a * a >= N) break;for (auto b : prime) {if (1ll * a * a + b * b * b >= N) break;for (auto c : prime) {ll val = 1ll * a * a + b * b * b + c * c * c * c;if (val >= N) break;s.insert(val);}}}vector<int> v(s.begin(), s.end());sort(v.begin(), v.end());// 将右边界跟新成一个比较大的数,方便维护v.push_back(int(1e9));int m = v.size();int t;cin >> t;// ----- 以下为二分的部分 -----while (t--) {int x;cin >> x;// 需要在 v 中找到 所有 <= x 的个数// 这里采用二分的第一种模版,找到 v 中第一个 > x 的下标// 也可以采用第二个模版,找到 v 中最后一个 <= x 的下标// 1.手写二分int l = 0, r = m - 1;while(l < r){int mid = l + r >> 1;if(v[mid] > x) r = mid;elsel = mid + 1;}cout << l << "\n";// 2. 也可以用库函数实现// int idx = upper_bound(v.begin(), v.end(), x) - v.begin(); // STL实现,返回 v 中第一个大于 x 的下标// cout << idx << "\n";}return 0;
}

这篇关于【秋招刷题打卡】Day02-二分系列之-二分查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085344

相关文章

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta