はいはい、ザコだち，又来到 pwp 的教学题了喵 qwq。昨天刚教了排序，如果有还没学会的现在爬回去补题喵 qwq。

咳咳，现在是今天的正经教学时间喵 qwq。後輩们以前多少都应该接触或者听说过二分法，这里的二分就是那个二分。算法中的二分法一般包括二分查找（折半搜索）和二分答案，这里先说到二分查找 qwq。对于一个有序的，或者说已经排完序的数组，要在里面查找一个数，是阔以通过二分查找把 O(n) 的查找时间压缩为 O(\log{n}) 的喵 pwp。

毕竟对于一个有序的数组或子数组 a_i(l \le i \le r)，这里先把有序先认为是从小到大的顺序，如果要在数组中查找 x，每次检查当前数组的中间位置 mid = \frac{l + r}{2}（数组长度为偶数时依照情况进行上取整或下取整），可以分成以下几种情况：

• 如果 a_{mid} = x，那就直接找到了喵，阔以退出这个流程了 qwq
• 如果 a_{mid} < x，那所有 a_i(i < mid) 都有 a_i < x 喵，那左半边就不用管啦，把 mid + 1 赋值给 l，继续重复流程
• 如果 a_{mid} > x，和第二种情况类似喵，这时候就不管右半边了，把 r 的值变成 mid - 1
• 重复上面的流程直到 a_{mid} = x（找到 x 了） 或者 l = r（没找到喵） 喵 pwp。

一般一个手写二分的核心代码阔能长这样 qwq:

int a[100005], n, x;

int L = 1, R = n;
while (L < R)
{
    int mid = L + R >> 1;
    if (a[mid] == x)
    {
        L = mid; //找到了就将 L 设定为查找到的位置下标 qwq
        break;
    }
    else if (a[mid] < x)
        L = mid + 1;
    else //a[mid] > x
        R = mid - 1;
}

当然除了查找一个数，二分也阔以 pwp：

查找大于 x 的第一个数，这里用的是 pwp 习惯的写法 qwq

int a[100005], n, x;

int L = 1, R = n + 1;
while (L < R)
{
    int mid = L + R >> 1;
    if (a[mid] < x)
        L = mid + 1;
    else //a[mid] >= x
        R = mid;
}

或者查找不大于 x 的最后一个数

int a[100005], n, x;

int L = 0, R = n;
while (L < R)
{
    int mid = L + R + 1 >> 1;
    if (a[mid] <= x)
        L = mid;
    else //a[mid] > x
        R = mid - 1;
}

网上也有各类好用的二分模板喵 qwq，也阔以找其它先輩们要 pwp。

好了，pwp 的经念完。现在阔以把下面的模板题做了 qwq。

给定一个长度为 n 的升序整数数组 a_i，后有 q 次询问，每次查询 x 在数组中出现的第一个位置，如果 x 不存在，输出 0。

第一行输入两个整数表示 n, q(1 \le n, q \le 10^5)。

接下来一行输入 n 个整数 a_i(-10^9 \le a_i \le 10^9)。

接下来 q 行是询问，每行输入一个整数 x(-10^9 \le x \le 10^9)。

对于 q 个询问中的每个询问，均输出一行一个整数表示该询问的结果。

提示？pwp

什喵提示？pwp

讲的这喵清楚怎喵还要提示？pwp