算法小记(二分)

题目描述:

输入 𝑛n 个不超过 109109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 𝑎1,𝑎2,…,𝑎𝑛a1​,a2​,…,an​，然后进行 𝑚m 次询问。对于每次询问，给出一个整数 𝑞q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1−1 。

代码:

package lanqiao;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] num = new int[n + 1];
        for(int i = 1;i <= n;i ++)
        {
            num[i] = sc.nextInt();
        }

        while(m -- > 0)
        {
            int target = sc.nextInt();
            int left = 1;
            int right = n;
            //二分模板
            while(left < right)
            {
                int mid = (left + right)/2;
                if(num[mid] < target){
                    left = mid + 1;
                }
                else
                {
                    right = mid;
                }
            }

            if(num[left] == target)
            {
                System.out.print(left + " ");
            }else{
                System.out.print(-1 + " ");
            }
        }
    }
}