İkili axtarış - 1#9017

İkili axtarış - 1 (Həll təhlili)

$x$ ədədinin sıralanmış massivdə neçə dəfə təkrarlandığını hesablamaq üçün upper_bound $(m, m + n, x)$ (m, m + n, x) – lower_bound $(m, m + n, x)$ (m, m + n, x) istifadə edilir. Bu funksiyaları STL kitabxanasından götürmək və ya (məsələn, Java üçün) özünüz yazmaq olar.

Bütün $n$ elementinin $0$-dan $n-1 $-ə qədərki indekslərdə olduğu halda, \textbf{lower_bound} və \textbf{upper_bound} funksiyaları \$0\$-dan \$n$ -ə qədər nəticə qaytara bilər. Buna görə ikili axtarış bu hədlərdə aparılmalıdır.

Alqoritmin reallaşdırılması

İş massivini elan edək.

#define MAX 1000000
int m[MAX];

Giriş məlumatlarını oxuyuruq.

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

$q$ sorğusunu ardıcıllıqla emal edirik. Hər bir sorğu üçün $x$ qiymətini oxuyuruq və onun $m$ massivində neçə dəfə təkrarlandığını çap edirik.

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

Alqoritmin reallaşdırılması — lower_bound və upper_bound funksiyaları

#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 reallaşdırılması

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 reallaşdırılması

import bisect

Giriş məlumatlarını oxuyuruq.

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

$q$ sorğusunu ardıcıllıqla emal edirik. Hər bir sorğu üçün $x$ qiymətini oxuyuruq və onun $lst$ massivində neçə dəfə təkrarlandığını çap edirik.

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