首页 > 其他分享 >11617 查找首次出现的位置 二分

11617 查找首次出现的位置 二分

时间:2024-09-30 16:44:26浏览次数:6  
标签:二分 读取 int 查询 11617 查找 数组

解决思路

 
  • 读取输入:读取数组和查询数。
 
  • 二分查找:对每个查询数进行二分查找,找到其在数组中第一次出现的位置。
 
  • 输出结果:输出每个查询数在数组中第一次出现的位置。
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 1e6 + 10;
    int a[N];
    int n, x;
    
    int main() {
        // 读取数组元素个数
        cin >> n;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        
        // 读取查询数个数
        int q;
        cin >> q;
        
        while (q--) {
            cin >> x;
            int L = 1, R = n, ans = -1;
            
            // 二分查找
            while (L <= R) {
                int mid = (L + R) / 2;
                if (a[mid] == x) {
                    ans = mid;
                    R = mid - 1; // 继续向左查找
                } else if (a[mid] < x) {
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            
            // 输出结果
            if (ans != -1) {
                cout << ans << " ";
            } else {
                cout << -1 << " ";
            }
        }
        
        return 0;
    }

     

标签:二分,读取,int,查询,11617,查找,数组
From: https://www.cnblogs.com/jyssh/p/18442138

相关文章

  • 二分图
    二分图定义:可以分为两个部分的图(称为左部和右部),同一个部分内没有边。由此得到:二分图是可以被二染色的图。若二分图\(G=(V,E)\)包含\(C\)个连通分量,则其二染色的方案为\(2^C\)。二分图的判定定理:一张无向图是二分图,当且仅当图中无奇环。推论:二分图的任意子图为......
  • [USACO03Open] Lost Cows(二分加树状数组)
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • rust二分搜索
    如果要二分搜索某个特定值,可以用binary_search:https://doc.rust-lang.org/stable/std/primitive.slice.html#method.binary_search如果要实现C++里的lower_bound和upper_bound类似的功能,可以用partition_point:https://doc.rust-lang.org/stable/std/primitive.slice.html#meth......
  • MySQL查找占用CPU过高的SQL
    作为DBA工作中都会遇到过数据库服务器CPU飙升的场景,我们该如何快速定位问题?又该如何快速找到具体是哪个SQL引发的CPU异常呢?下面我们说两个方法。聊聊MySQL中如何快速定位占用CPU过高的SQL。技术人人都可以磨炼,但处理问题的思路和角度各有不同,希望这篇文章可以抛砖引玉。 以一......
  • 使用二分法爆破数据库名
    这一篇是基于dvwa下的SQL盲注(SDLInjection(Blind),在已知数据库存在和SDL盲注可行的前提下进行更深一步的操作。这里,我们将会通过python来爆破数据库名。1.python连接数据库。(1)首先我们需要查看自己的python是否已经已经安装了pymysql库,如果没有安装,可以通过Win+R打开命令行......
  • 二分图
    定义两个点集,点集内部没有连边的图称为二分图。二分图最大匹配选中最多的边,满足每个点只被选到一次,即最大边匹配点。考虑网络流建模。每个点只能用一次,\(S\)向左边的点连一条流量为\(1\)的边,右边的点向\(T\)连一条流量为\(1\)的边,就可以保证这个要求。然后两个点集之间......
  • 二分图最大匹配/二分图最大权匹配
    二分图最大匹配匈牙利算法思路算法核心:找“增广路”遍历所有左侧点,每次进行一下流程:尝试去寻找一个右侧点来匹配;若该右侧点还没有匹配的左侧点,则找到了,回溯。否则进入改右侧点的匹配左侧点,回到1。代码constintN=505;intn,m,tag;vector<int>g[N];intmatch[N]......
  • CF1592F2-Alice and Recoloring 2-分析、二分图
    link:https://codeforces.com/contest/1592/problem/F2题意:给定一个\(n\)行\(m\)列的目标矩阵,矩阵元素只有W或B,并且你有一个初始矩阵,元素全为W。现在你可以矩阵实施以下操作:使用一块钱,选定一个包含\((1,1)\)的子矩阵,把矩阵中的元素全部反转(W变B,B变W)。使用......
  • codeforces round 971(div4)E(二分答案,禁用数学方法)
    解题历程:开始想的是用数学公式的方法,利用公式推出二次函数,再求出根,再用根求出答案,检查了一个小时,结果怎么改都有细微的偏差,最后发现答案先单调递减在单调递增,那么可以用二分答案的方法查找最小的答案,二分对细节的处理要求比较高,于是在二分中加入了一个限制,当二分的区间小于5时,就......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素、977.有序数组的平方。
    704.二分查找总结:防止int溢出:classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;while(left<=right){intmiddle=(left+right)/2;//intmid=(right-left)/......