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

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

前言

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

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

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

在这里插入图片描述

小屋day02

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

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

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

引言

举个二分的例子：

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

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

通过二分搜索能够有效的帮原本 $O (n)$ 遍历数组的时间复杂度降为 $\log(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) // 2
        if 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; // 注意这里要多加 1
        if (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;// 注意这里要多加 1
        if (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 # 注意这里要多加 1
        if 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) // 2
                if check(mid):
                    r = mid # check函数代表你需要进行的判断操作
                            # 最终的答案会满足check条件
                else:
                    l = mid + 1 # 一定是这么写 不用多想
            if l >= n or nums[l] != target: # 代表没有找到答案
                return -1
            return l # 此时的 l 为答案 (l == r)
        def bsearch_2(l, r): # 找到最后一个 <= target的位置
            def check(index):
                if nums[index] <= target: # 说明当前 nums[mid] 太小了，答案下标应该 >= index, 所以返回 True 缩小左端点
                    return True
                return False
            # l 为左端点，r 为右端点，都是闭区间
            # 使用时只需修改check函数即可
            while l < r:
                mid = (l + r + 1) // 2 # 注意这里要多加 1
                if check(mid):
                    l = mid # check函数代表你需要进行的判断操作
                            # 最终的答案会满足check条件
                else:
                    r = mid - 1 # 一定是这么写 不用多想
            if l >= n or nums[l] != target: # 代表没有找到答案
                return -1
            return 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; // 注意这里要多加 1
            if (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 = a^2 + b^3 + c^4$ ，其中 $a, b, c$ 都为质数。于是 LYA 想知道在 $\sim n$ 中有多少个这样的神奇数字呢，请你告诉 LYA。

输入格式

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

接下来有 $t$ 行，每行为一个整数 $n$ 。

输出格式

输出为 $t$ 行，每行为一组答案。

样例输入

样例输出

1
2
3

数据范围

$1 < t < 10^5$
$\leq n < 10^6$

题解

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

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

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

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

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

时间复杂度 $\log n)$ ，空间复杂度 $O (n)$ 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()
import bisect

prime = []
N = 10 ** 6 + 1
st = [False] * N

for 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:
        break
    for b in prime:
        if a * a + b ** 3 >= N:
            break
        for c in prime:
            val = a ** 2 + b ** 3 + c ** 4
            if val >= N:
                break
            s.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 - 1
    while l < r:
    	mid = (l + r) // 2
    	if v[mid] > x:
    		r = mid
    	else:
    		l = mid + 1
    print(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; 
            	else
            		L = mid + 1;
            }
          
            System.out.println(L);
        }
    }
}

#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;
          	else
          		l = 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-二分系列之-二分查找

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

前言

小屋day02

引言

二分模版

版本1

版本2

什么时候使用版本1 or 2？

🎀 模版题

题目描述

解题思路

参考代码

🍰 笔试真题

神奇数字

题目描述

输入格式

输出格式

样例输入

样例输出

数据范围

题解

参考代码

网站公告

今日签到

热门文章

最新发布