查找（洛谷P2249题题解，C++语言描述）

超、凢脫俗 2022-10-22 04:25 152阅读 0赞

# 题目要求 #

[题目链接][Link 1]

![在这里插入图片描述][20210404005926974.png]

# 分析 #

可以用内置函数直接解：`lower_bound(a.begin(), a.end(), i)`

如果自己写二分查找也行，注意是第一个出现的，所以不注意的话求的可不是第一个呀！

另，Java代码如下，TLE+MLE，垃圾语言！

import java.io.*;
    import java.util.*;
    
    // TLE+MLE
    public class Main {
        
    
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            String[] line = bf.readLine().split("\\s+");
            int n = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]);
            List<Integer> list = new ArrayList<>(n);
            line = bf.readLine().split("\\s+");
            for (int i = 0; i < n; i++) {
        
                list.add(Integer.parseInt(line[i]));
            }
            line = bf.readLine().split("\\s+");
            for (int i = 0; i < m; i++) {
        
                System.out.print(list.indexOf(Integer.parseInt(line[i])) + " ");
            }
            bf.close();
        }
    
    }

# AC代码 #

#include <iostream>
    
    using namespace std;
    
    int nums[1000001];
    
    int main() {
        
        int n, m, query;
        cin >> n >> m;
        // 因为结果计算的下标是从1开始的
        for (int i = 1; i <= n; i++) {
        
            cin >> nums[i];
        }
        for (int i = 0; i < m; i++) {
        
            cin >> query;
            int result = lower_bound(nums+1, nums+n+1, query)-nums;
            cout << ((query == nums[result]) ? result : -1) << " ";
        }
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P2249
[20210404005926974.png]: /images/20221022/f1a5f4a5e290416c9708748f313388e0.png