Разбор

Количество вхождений числа $x$ в отсортированный массив равно upper_bound $(m, m + n, x)$ — lower_bound $(m, m + n, x)$ . Эти функции можно взять из библиотеки шаблонов STL или реализовать самостоятельно (например, для Java).

Пусть все $n$ элементов массива $m$ находятся в ячейках от $0$ до $n - 1$ . В этом случае функции lower_bound и upper_bound могут возвращать значения от $0$ до $n$ . Поэтому бинарный поиск следует выполнять в этих пределах.

Реализация алгоритма

Объявим рабочий массив.

#define MAX 1000000
int m[MAX];

Читаем входные данные.

scanf("%d %d", &n, &q);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Последовательно обрабатываем $q$ запросов. Для каждого запроса считываем значение $x$ и выводим количество его вхождений в массив $m$ .

for (i = 0; i < q; i++)
{
  scanf("%d", &x);
  res = upper_bound(m, m + n, x) - lower_bound(m, m + n, x);
  printf("%d\n", res);
}

Реализация алгоритма — собственные функции lower_bound, upper_bound

#include <cstdio>
#include <algorithm>
#include <stdio.h>
#define MAX 1000000

int i, n, q, x, res;
int m[MAX];

int my_lower_bound(int *m, int start, int end, int x)
{
  while (start < end)
  {
    int mid = (start + end) / 2;
    if (x <= m[mid])
      end = mid;
    else
      start = mid + 1;
  }
  return start;
}

int my_upper_bound(int *m, int start, int end, int x)
{
  while (start < end)
  {
    int mid = (start + end) / 2;
    if (x >= m[mid])
      start = mid + 1;
    else
      end = mid;
  }
  return start;
}

int main(void)
{
  scanf("%d %d", &n, &q);
  for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

  for (i = 0; i < q; i++)
  {
    scanf("%d", &x);
    res = my_upper_bound(m, 0, n, x) – my_lower_bound(m, 0, n, x);
    printf("%d\n", res);
  }
  return 0;
}

Java реализация

import java.util.*;
import java.io.*;

public class Main 
{
  static int my_lower_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x <= m[mid])
        end = mid;
      else
        start = mid + 1;
    }
    return start;
  }

  static int my_upper_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x >= m[mid])
        start = mid + 1;
      else
        end = mid;
    }
    return start;
  }
	
  public static void main(String[] args) 
  {
    FastScanner con = 
      new FastScanner(new InputStreamReader(System.in));    
    int n = con.nextInt();
    int q = con.nextInt();
    int m[] = new int[n];
    for(int i = 0; i < n; i++)
      m[i] = con.nextInt();
    
    for(int i = 0; i < q; i++)
    {
      int x = con.nextInt();
      int res = my_upper_bound(m,0,n,x) - my_lower_bound(m,0,n,x); 
      System.out.println(res);
    }
  }
}

class FastScanner
{
  private BufferedReader br;
  private StringTokenizer st;
 
  public FastScanner(InputStreamReader reader) 
  {
    br = new BufferedReader(reader);
  }
 
  public String next() 
  {
    while (st == null || !st.hasMoreTokens()) 
    {
      try 
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) 
      {
        e.printStackTrace();
      }
    }
    return st.nextToken();
  }

  public int nextInt() 
  {
    return Integer.parseInt(next());
  }
  
  public double nextDouble() 
  {
    return Double.parseDouble(next());
  }
 
  public void close() throws Exception 
  {
    br.close();
  }
}