Binary search (Editorial)

In this problem, it is required to find a number in a sorted array, which can be done using binary search.

Let $m$ be a sorted array of length $n$ , consisting of integers. The function binary_search $(m, m + n, x)$ (m, m + n, x) returns true if number $x$ is present in the array. Reading the input array takes $O (n)$ , and handling $q$ queries takes $O (q \cdot l o g_{2} n)$ O(q \cdot log_2n).

The lower_bound function returns a pointer to the first position where the element $x$ can be inserted without violating the sorted order of the array.

The upper_bound function returns a pointer to the last position where the element $x$ can be inserted without violating the sorted order of the array.

If lower_bound $(m, m + n, x) \neq =$ (m, m + n, x) \ne~upper_bound $(m, m + n, x)$ (m, m + n, x), then the number $x$ is present in the array. Otherwise, the number $x$ is not in the array.

The Java function Arrays.binarySearch() returns the index of the found element in the array. If the array contains multiple identical keys, it returns the index of any one of them.

If $x$ is not present in the array $m$ , the function Arrays.binarySearch $(m, x)$ returns the value $- p os - 1$ -pos - 1, where $p os$ is the index of the first element greater than $x$ . If $x$ is greater than all elements in the array $m$ , then $p os = m . l e n g t h$ pos = m.length.

The bisect function in Python is used for performing binary search in sorted sequences. It helps find the insertion point for an element in a sorted list to maintain the order of the list. This can be useful, for example, for optimizing the insertion of new elements into an ordered list or for determining where to insert an element in an array to keep it sorted.

bisect provides two main functions:

bisect.bisect_left $(l s t, x, l o = 0, hi = l e n (l s t))$ (lst, x, lo = 0, hi = len(lst)). This function finds the insertion point for element $x$ in the sorted list $l s t$ . If the element is already present in the list, bisect_left will return the index of the first occurrence of $x$ . If the element is absent, the function will return the index where $x$ can be inserted without breaking the sorting order.
bisect.bisect_right $(l s t, x, l o = 0, hi = l e n (l s t))$ (lst, x, lo = 0, hi = len(lst)). Similar to bisect_left, but it returns the index for inserting element $x$ after the existing occurrences of $x$ in the list $l s t$ .

Both functions accept optional arguments $l o$ and $hi$ , which define the search range within the list. By default, $l o = 0$ lo = 0, and $hi = l e n (l s t)$ hi = len(lst).

Implementation of own binary search. Suppose we need to find the element $x$ in the array $m$ within the range $[s t a r t; e n d]$ [start; end]. Divide the segment in half, setting $mi d = (s t a r t + e n d) /2$ mid = (start + end) / 2. If $x > m [mi d]$ x > m[mid], then the element $x$ is in the range $[mi d + 1; e n d]$ [mid + 1; end]. Otherwise, continue the search in the range $[s t a r t; mi d]$ [start; mid].

Data structures set. Insert the numbers from the input array into a $se t < in t > s$ set<int> s. If a number appears multiple times in the array, it will be added to the set only once. The result of checking for the presence of a given element in the array remains unchanged.

An element $x$ is present in the set (and in the input array) if $s . f in d (x)! = s . e n d ()$ s.find(x) != s.end().

Inserting elements from the input array into the set takes O(nlog2n), and processing $q$ queries takes $O (q \cdot l o g_{2} n)$ O(q \cdot log_2n).

Algorithm implementation — $O (n + q \cdot l o g_{2} n)$ O(n + q \cdot log_2n)

Declare an array.

#define MAX 1000000
int m[MAX];

Read the input data.

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

Process $q$ queries sequentially.

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

Read the value of $x$ .

  scanf("%d", &x);

A number $x$ is present in the array $m$ if binary_search returns true.

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

Algorithm implementation — lower_bound, upper_bound

Declare an array.

#define MAX 1000000
int m[MAX];

Read the input data.

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

Process $q$ queries sequentially.

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

Read the value of $x$ .

  scanf("%d", &x);

A number $x$ is present in the array $m$ if lower_bound $(m, m + n, x) \neq =$ (m, m + n, x) \ne~upper_bound $(m, m + n, x)$ (m, m + n, x)

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

Algorithm implementation — own binary search

Declare an array.

#define MAX 1000000
int m[MAX];

The my_bin_search function implements a binary search and returns $1$ , if the number $x$ is present in the array $m$ within the range $[s t a r t; e n d]$ [start; end].

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

Perform a binary search on the interval $[s t a r t; e n d]$ [start; end].

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

C++

Return the result.

  return m[start] == x;
}

The main part of the program. Read the input data.

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

Process $q$ queries sequentially.

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

Read the value of $x$ .

  scanf("%d", &x);

A number $x$ is present in the array $m$ if my_bin_search returns $1$ .

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

Algorithm implementation — set, $O (n \cdot l o g_{2} n + q \cdot l o g_{2} n$ O(n \cdot log_2n + q \cdot log_2n

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

C++

Java implementation — own binary search

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

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

Java

Python implementation

Import the bisect module.

import bisect

Read the input data.

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

Process $q$ queries sequentially.

for _ in range(q):

Read the value of $x$ .

  x = int(input())

A number $x$ is present in the list $l s t$ if bisect_left $(l s t, x) \neq =$ (lst, x) \ne~bisect_right $(l s t, x)$ (lst, x)

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

Python implementation — own binary search

The my_bin_search function implements a binary search:

If the number $x$ is not present in the list $a$ , the function returns $- 1$ .
Otherwise, it returns the position of the number $x$ in the list $a$ .

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

Perform a binary search over the interval $[s t a r t; e n d] = [0; l e n (a) - 1]$ [start; end] = [0; len(a) - 1].

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

Return the result.

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

The main part of the program. Read the input data.

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

Process $q$ queries sequentially.

for _ in range(q):

Read the value of $x$ .

  x = int(input())

Perform a binary search. Print the corresponding result.

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