Разбор

В данной задаче требуется найти число в отсортированном массиве, что можно сделать с помощью бинарного поиска.

Пусть $m$ — отсортированный массив длины $n$ , состоящий из целых чисел. Функция binary_search $(m, m + n, x)$ возвращает true, если число $x$ присутствует в массиве. Входной массив читается за $O (n)$ , $q$ запросов выполняются за $O (q \cdot l o g_{2} n)$ .

Функция lower_bound возвращает указатель на первую позицию, в которую можно вставить элемент $x$ без нарушения свойства отсортированности массива.

Функция upper_bound возвращает указатель на последнюю позицию, в которую можно вставить элемент $x$ без нарушения свойства отсортированности массива.

Если lower_bound $(m, m + n, x) \neq =$ upper_bound $(m, m + n, x)$ , то число $x$ присутствует в массиве. В противном случае числа $x$ в массиве нет.

Java функция Arrays.binarySearch() возвращает индекс найденного элемента в массиве. Если массив содержит несколько одинаковых ключей, то возвращается индекс любого из них.

Если $x$ отсутствует в массиве $m$ , то функция Arrays.binarySearch $(m, x)$ возвращает значение $- p os - 1$ , где $p os$ — индекс первого элемента, большего $x$ . Если $x$ больше всех элементов массива $m$ , то $p os = m . l e n g t h$ .

Функция bisect в Python используется для выполнения бинарного поиска в отсортированных последовательностях. Она помогает найти место вставки элемента в отсортированный список, чтобы сохранить порядок сортировки. Это может быть полезно, например, для оптимизации добавления новых элементов в упорядоченный список или для определения, куда вставить элемент в массив, чтобы сохранить сортировку.

bisect предоставляет две основные функции:

bisect.bisect_left $(l s t, x, l o = 0, hi = l e n (l s t))$ . Эта функция находит точку вставки для элемента $x$ в отсортированном списке $l s t$ . Если элемент уже присутствует в списке, то bisect_left вернет индекс первого вхождения $x$ . Если элемент отсутствует, функция вернет индекс, где можно вставить $x$ , не нарушив порядок сортировки.
bisect.bisect_right $(l s t, x, l o = 0, hi = l e n (l s t))$ . Аналогична bisect_left, но возвращает индекс для вставки элемента $x$ после существующих вхождений $x$ в список $l s t$ .

Обе функции принимают необязательные аргументы $l o$ и $hi$ , которые определяют диапазон поиска в списке. По умолчанию $l o = 0$ , а $hi = l e n (l s t)$ .

Реализация собственного бинарного поиска. Пусть требуется найти элемент $x$ в массиве $m$ на промежутке $[s t a r t; e n d]$ . Делим отрезок пополам, положим $mi d = (s t a r t + e n d) /2$ . Если $x > m [mi d]$ , то элемент $x$ находится на отрезке $[mi d + 1; e n d]$ . Иначе следует продолжить поиск на отрезке $[s t a r t; mi d]$ .

Структура данных set. Занесем числа из входного массива в структуру данных $se t < in t > s$ . Если некоторое число присутствует в массиве несколько раз, в set оно будет добавлено только один раз. При этом результат запроса на присутствие заданного элемента в массиве не изменится.

Элемент $x$ присутствует во множестве (во входном массиве), если $s . f in d (x)! = s . e n d ()$ .

Элементы входного массива заносятся во множество за $O (n \cdot l o g_{2} n)$ , $q$ запросов выполняются за $O (q \cdot l o g_{2} n)$ .

Реализация алгоритма — $O (n + q \cdot l o g_{2} n)$

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

#define MAX 1000000
int m[MAX];

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

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

Последовательно обрабатываем $q$ запросов.

for (i = 0; i < q; i++)
{

Читаем число $x$ .

  scanf("%d", &x);

Число $x$ присутствует в массиве $m$ , если функция binary_search возвращает true.

  if (binary_search(m, m + n, x) == 1)
    puts("YES");
  else
    puts("NO");
}

Реализация алгоритма — lower_bound, upper_bound

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

#define MAX 1000000
int m[MAX];

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

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

Последовательно обрабатываем $q$ запросов.

for (i = 0; i < q; i++)
{

Читаем число $x$ .

  scanf("%d", &x);

Число $x$ присутствует в массиве $m$ , если lower_bound $(m, m + n, x) \neq =$ upper_bound $(m, m + n, x)$

  if (lower_bound(m, m + n, x) != upper_bound(m, m + n, x))
    puts("YES");
  else
   puts("NO");
}

Реализация алгоритма — собственный бинарный поиск

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

#define MAX 1000000
int m[MAX];

Функция my_bin_search реализует бинарный поиск и возвращает $1$ , если число $x$ присутствует в массиве $m$ в диапазоне $[s t a r t; e n d]$ .

int my_bin_search(int *m, int start, int end, int x)
{

Запускаем бинарный поиск на интервале $[s t a r t; e n d]$ .

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

Возвращаем результат.

  return m[start] == x;
}

Основная часть программы. Читаем входные данные.

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

Последовательно обрабатываем $q$ запросов.

for (i = 0; i < q; i++)
{

Читаем число $x$ .

  scanf("%d", &x);

Число $x$ присутствует в массиве $m$ , если my_bin_search возвращает $1$ .

  if (my_bin_search(m, 0, n - 1, x))
    puts("YES");
  else
    puts("NO");
}

Реализация алгоритма — set, $O (n \cdot l o g_{2} n + q \cdot l o g_{2} n$

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

int i, n, q, x;
set<int> s;

int main(void)
{
  scanf("%d %d", &n, &q);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &x);
    s.insert(x);
  }

  for (i = 0; i < q; i++)
  {
    scanf("%d", &x);
    if (s.find(x) != s.end())
      puts("YES");
    else
      puts("NO");
  }
  return 0;
}

Java реализация — собственный бинарный поиск

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

public class Main 
{
  static int my_bin_search(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 (m[start] == x) ? 1 : 0;
  }

  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();
      if(my_bin_search(m,0,n-1,x) == 1)
        System.out.println("YES");
      else
    	System.out.println("NO");
    }
  }
}

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();
  }
}

Java реализация — Arrays.binarySearch

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

public class Main 
{
  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();
      if(Arrays.binarySearch(m, x) >= 0)
        System.out.println("YES");
      else
    	System.out.println("NO");
    }
  }
}

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();
  }
}

Python реализация

Импортируем модуль bisect.

import bisect

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

n, q = map(int,input().split())
lst = list(map(int,input().split()))

Последовательно обрабатываем $q$ запросов.

for _ in range(q):

Читаем число $x$ .

  x = int(input())

Число $x$ присутствует в массиве $m$ , если bisect_left $(l s t, x) \neq =$ bisect_right $(l s t, x)$

  if bisect.bisect_left(lst, x) != bisect.bisect_right(lst, x):
    print("YES")
  else:
    print("NO")

Python реализация — собственный бинарный поиск

Функция my_bin_search реализует бинарный поиск:

если число $x$ отсутствует в списке $a$ , то функция возвращает $- 1$ .
иначе возвращается позиция числа $x$ в списке $a$ .

def my_bin_search(a, x):
  start = 0
  end = len(a) – 1

Запускаем бинарный поиск на интервале $[s t a r t; e n d] = [0; l e n (a) - 1]$ .

  while start < end:
    mid = (start + end) // 2;
    if x > a[mid]:
      start = mid + 1;
    else:
      end = mid;

Возвращаем результат.

  if a[start] == x:
    return start
  else:
    return -1;

Основная часть программы. Читаем входные данные.

n, q = map(int,input().split())
lst = list(map(int,input().split()))

Последовательно обрабатываем $q$ запросов.

for _ in range(q):

Читаем число $x$ .

  x = int(input())

Запускаем бинарный поиск. Выводим соответствующий ответ.

  if my_bin_search(lst,x) != -1:
    print("YES")
  else:
    print("NO")