Бінарний пошук - 1#9017

Бінарний пошук - 1 (Розбір)

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

Нехай всі $n$ елементів масиву $m$ знаходяться в осередках від $0$ до $n - 1$ 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

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

Java

Python реалізація

import bisect

Читаємо вхідні дані.

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

Послідовно обробляємо $q$ запитів. Для кожного запиту читаємо значення $x$ і виводимо кількість його входжень в список $l s t$ .

for _ in range(q):
  x = int(input())
  res = bisect.bisect_right(lst, x) - bisect.bisect_left(lst, x)
  print(res)