首页 > 其他分享 >二分搜索与二分答案

二分搜索与二分答案

时间:2022-12-29 20:36:14浏览次数:38  
标签:二分 int mid else while 搜索 答案 check

二分的本质

序列要满足有序性或者有有序的性质:
有单调性一定可以二分,没有单调性也可以进行二分;下面是两个模板;
img
tips:mid=男左女右,男加1

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

数的范围(详细的二分过程)

问题描述:

给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。

解决的思路:
img
代码:

#include<iostream>
using namespace std;
const int N=100010;
int q[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }

    while(m--){
        int x;
        cin>>x;
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(q[mid]>=x) r=mid;
            else l=mid+1;
        }
        if(q[l]!=x) cout<<"-1 -1"<<endl;
        else{
            cout<<l<<" ";
            int l=0,r=n-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(q[mid]<=x)l=mid;
                else r=mid-1;
            }
            cout<<r<<endl;
        }
    }
    return 0;
}

标签:二分,int,mid,else,while,搜索,答案,check
From: https://www.cnblogs.com/ai-researcher/p/17012895.html

相关文章

  • 二分算法
    二分算法题目合集题目来源难度袋子里数目最少的球力扣中等礼盒的最大甜蜜度力扣中等两球之间的磁力力扣中等机器人跳跃问题Acwing中等分......
  • 查找蓝牙WiFi功能,搜索名字并列举出来
    先有一个概念,蓝牙分为普通蓝牙和低功耗(BLE)蓝牙,低功耗蓝牙激活时信号和普通蓝牙信号一样,低功耗时必须搜索低功耗蓝牙信号如果使用普通代码搜索,不能搜索到低功耗蓝牙信号......
  • pytorch:二分类时的loss选择
    PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用这里就总结一下使用PyTorch做二分类时的几种情况:总体上来讲,有三种实现形式:最后分类层降至一维,使用sigmo......
  • KG4Py:Python代码知识图谱和语义搜索的工具包
    如何构建Python的代码知识图谱,又该如何进行搜索呢?现在的项目程序中存在着大量重复的代码片段,尤其是在软件开发的时候。在本文中,我们提出了一个工具包(KG4Py),用于在GitHub存储......
  • 二分查找
    一、二分查找1.二分查找方法概述二分查找是针对有序数组的一种查找方式。是利用(letf+right)/2=mid的方式来对半缩短搜索范围的一种方法,一次查找,搜索的范围就会减半。相......
  • 算法刷题 Day 1 | 704.二分查找 & 27.移除元素
    今天是开始刷题的第一天,就像背单词书又从Abandon开始了一样,但是这次一定要坚持下来。第一天的内容是熟悉的数组,先来看第一题二分查找704.二分查找题目链接:https://leetc......
  • 二分查找(leetcode easy 704)、移除元素(leetcode easy 27)
    二分查找题目链接:https://leetcode.cn/problems/binary-search/思路:暴力法:直接遍历一边数组查找元素.此方法适用于任何数组查找.(时间复杂度O(n)、空间复杂度O(......
  • 刷刷刷Day1| LeetCode704. 二分查找,27. 移除元素
    704.二分查找LeetCode题目要求给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。......
  • 二分法查找算法优化
    摘要:使用位运算和减少计算次数的技巧优化二分查找算法。在《算法——二分法查找》的二分法实现源码binarySearch_2实现中,可以发现计算了两次mid,那有没有办法计算一次呢?另......
  • python 实现抖音通过关键字搜索下载短视频
    在日常生活中,随着短视频的发展,大家使用抖音进行数据搜索,也占了一大部分,今天给大家带来的文章抖音根据关键词进行视频下载有什么作用呢?其实很多时候我们制作视频,写脚本,都需要......