Algorithms · 28

Binary Search

Throw away half of a sorted range at a time to find a value, or the first position that meets a condition.

Binary search looks at the middle of a sorted list and throws away the half that cannot hold the answer, again and again.
The example below has scores sorted from low to high, and for each queried score x it finds the first position whose value is x or more.
That position is also the number of scores below x, so it prints that number and then yes if someone scored exactly x, or no if not.

def lower_bound(a, x):    lo, hi = 0, len(a)  # 답은 lo부터 hi까지 가운데 어딘가    while lo < hi:        mid = (lo + hi) // 2        if a[mid] < x:            lo = mid + 1  # mid와 그 왼쪽은 모두 x보다 작아요        else:            hi = mid  # mid와 그 오른쪽은 모두 x 이상이에요    return lo  # x 이상인 첫 자리(없으면 len(a))  n, q = map(int, input().split())scores = list(map(int, input().split()))for x in map(int, input().split()):    pos = lower_bound(scores, x)  # x보다 낮은 점수의 개수이기도 해요    found = pos < n and scores[pos] == x    print(pos, "yes" if found else "no")

function lowerBound(a, x) {  let lo = 0, hi = a.length; // 답은 lo부터 hi까지 가운데 어딘가  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요    else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요  }  return lo; // x 이상인 첫 자리(없으면 a.length)} const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n] = lines[0].split(" ").map(Number);const scores = lines[1].trim().split(" ").map(Number);for (const x of lines[2].trim().split(" ").map(Number)) {  const pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요  const found = pos < n && scores[pos] === x;  console.log(pos, found ? "yes" : "no");}

import { readFileSync } from "node:fs"; function lowerBound(a: number[], x: number): number {  let lo = 0, hi = a.length; // 답은 lo부터 hi까지 가운데 어딘가  while (lo < hi) {    const mid: number = Math.floor((lo + hi) / 2);    if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요    else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요  }  return lo; // x 이상인 첫 자리(없으면 a.length)} const lines: string[] = readFileSync(0, "utf8").split("\n");const [n] = lines[0].split(" ").map(Number);const scores: number[] = lines[1].trim().split(" ").map(Number);for (const x of lines[2].trim().split(" ").map(Number)) {  const pos: number = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요  const found: boolean = pos < n && scores[pos] === x;  console.log(pos, found ? "yes" : "no");}

import java.util.Scanner; public class Main {    static int lowerBound(int[] a, int x) {        int lo = 0, hi = a.length; // 답은 lo부터 hi까지 가운데 어딘가        while (lo < hi) {            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요            if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요            else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요        }        return lo; // x 이상인 첫 자리(없으면 a.length)    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt(), q = sc.nextInt();        int[] scores = new int[n];        for (int i = 0; i < n; i++) scores[i] = sc.nextInt();        for (int i = 0; i < q; i++) {            int x = sc.nextInt();            int pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요            boolean found = pos < n && scores[pos] == x;            System.out.println(pos + " " + (found ? "yes" : "no"));        }    }}

using System; class Program{    static int LowerBound(int[] a, int x)    {        int lo = 0, hi = a.Length; // 답은 lo부터 hi까지 가운데 어딘가        while (lo < hi)        {            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요            if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요            else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요        }        return lo; // x 이상인 첫 자리(없으면 a.Length)    }     static void Main()    {        int n = int.Parse(Console.ReadLine().Split(' ')[0]);        int[] scores = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), int.Parse);        foreach (string s in Console.ReadLine().Trim().Split(' '))        {            int x = int.Parse(s);            int pos = LowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요            bool found = pos < n && scores[pos] == x;            Console.WriteLine(pos + " " + (found ? "yes" : "no"));        }    }}

#include <iostream>#include <vector> int lowerBound(const std::vector<int> &a, int x) {    int lo = 0, hi = a.size(); // 답은 lo부터 hi까지 가운데 어딘가    while (lo < hi) {        int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요        if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요        else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요    }    return lo; // x 이상인 첫 자리(없으면 a.size())} int main() {    int n, q;    std::cin >> n >> q;    std::vector<int> scores(n);    for (int &s : scores) std::cin >> s;    for (int i = 0; i < q; i++) {        int x;        std::cin >> x;        int pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요        bool found = pos < n && scores[pos] == x;        std::cout << pos << ' ' << (found ? "yes" : "no") << '\n';    }}

#include <stdio.h> int lower_bound(const int *a, int n, int x) {    int lo = 0, hi = n; // 답은 lo부터 hi까지 가운데 어딘가    while (lo < hi) {        int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요        if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요        else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요    }    return lo; // x 이상인 첫 자리(없으면 n)} int main(void) {    int n, q;    static int scores[10000];    scanf("%d %d", &n, &q);    for (int i = 0; i < n; i++) scanf("%d", &scores[i]);    for (int i = 0; i < q; i++) {        int x;        scanf("%d", &x);        int pos = lower_bound(scores, n, x); // x보다 낮은 점수의 개수이기도 해요        int found = pos < n && scores[pos] == x;        printf("%d %s\n", pos, found ? "yes" : "no");    }    return 0;}

lowerBound(a, x){    lo = 0; // 답은 lo부터 hi까지 가운데 어딘가    hi = a.Count;    while (lo < hi)    {        mid = Mathf.Quot(lo + hi, 2);        if (a[mid] < x)        {            lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요        }        else        {            hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요        }    }    return lo; // x 이상인 첫 자리(없으면 a.개수)} first = Console.ReadNumbers();n = first[0];scores = Console.ReadNumbers();foreach (x in Console.ReadNumbers()){    pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요    found = pos < n && scores[pos] == x;    Console.WriteLine(pos + " " + (found ? "yes" : "no"));}

stdin

7 5
40 55 55 70 82 82 95
55 60 82 100 10

stdout

1 yes
3 no
4 yes
7 no
0 no

Key points

When a list is sorted, one look at the middle rules out half of it.
If the middle is less than x, everything to its left is less than x too; if the middle is x or more, so is everything to its right.
The example's lower_bound returns the first position whose value is x or more.
If the value there equals x, then x is present, and among equal values it is the first one.
If there is no such value, it returns the length n.
One promise holds through the whole loop: everything left of lo is less than x, and everything from hi onward is x or more.
At the start (lo = 0, hi = n) both sides are empty, so it is true, and lo = mid + 1 and hi = mid never break it.
So the place where lo and hi meet is the answer.
While lo < hi, mid is always less than hi.
So whether you do lo = mid + 1 or hi = mid, the range shrinks by at least one, and the loop must end.
The range halves every time, so even a million items need at most 20 looks.
Measured on our judge with 10,000 scores and 10,000 queries: a Python solution that counts from the front took over 3 seconds, and binary search took about 0.02 s.
It is not only for finding values.
For any condition that is false for a while and then true from some position on, the same method finds the first position where the condition is true.
In the example the condition is "the value is x or more".

How each language writes it

Python	`mid = (lo + hi) // 2`. Built in: `import bisect` — `bisect.bisect_left(a, x)` is the first position with x or more (the same as the example's function), `bisect.bisect_right(a, x)` is the first position greater than x
JavaScript	`const mid = Math.floor((lo + hi) / 2);` — `/` gives a fraction, so always round down. There is no built-in binary search, so write it yourself
TypeScript	Same as JavaScript
Java	`int mid = lo + (hi - lo) / 2;`. The built-in `Arrays.binarySearch(a, x)` returns the position if found and `-(insertion point) - 1` if not (60 in the example's scores gives `-4`). With equal values there is no promise which of them you get (here 82 gives `5`, not the first one, 4). For lists use `Collections.binarySearch`
C#	`int mid = lo + (hi - lo) / 2;`. The built-in `Array.BinarySearch(a, x)` returns a negative number if not found, and `~` turns it into the insertion point (60 gives `-4`, and `~(-4)` is `3`). With equal values it may not be the first one (82 gives `5`). For lists use `list.BinarySearch(x)`
C++	`std::lower_bound(v.begin(), v.end(), x) - v.begin()` from `#include <algorithm>` is the same as the example's function. The first position greater than x is `std::upper_bound`; to learn only whether x is present, `std::binary_search`
C	`int mid = lo + (hi - lo) / 2;`. `bsearch(&x, a, n, sizeof a[0], cmp)` from `<stdlib.h>` returns only the address of an equal value or `NULL`, so it cannot find "the first position with x or more". Write the loop yourself as in the example
Craykon	`mid = Mathf.Quot(lo + hi, 2);` — `/` gives a fraction, and `a[1.5]` stops with "Use a whole-number index inside [ ]". There is no built-in binary search, so write it yourself

Common mistakes

Narrowing with `lo = mid` never ends

a = [10, 20, 30]
lo, hi = 0, 2  # find the last position with 20 or less
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] <= 20:
        lo = mid
    else:
        hi = mid - 1
print(lo)

→ It never ends. At lo = 1, hi = 2, mid is 1 again and the range stops shrinking

In the form that uses lo = mid, round the middle up (mid = (lo + hi + 1) // 2).
Then it prints 1 and ends.
Rather than mixing forms, it is safer to learn the one form in the example (lo = mid + 1, hi = mid).

`(lo + hi) / 2` overflowedJava · C# · C · C++

int lo = 1500000000, hi = 2000000000;
int mid = (lo + hi) / 2;
System.out.println(mid);

→ -397483648 — lo + hi went past the end of int (about 2.1 billion) and turned negative. C# gives the same value. In C and C++, overflowing an int is undefined behaviour: nothing is promised about what happens. Our judge happened to print the same value, but do not count on it

Write int mid = lo + (hi - lo) / 2; and you get 1750000000.
It is rare with array indexes, but you meet it at once when halving a range such as 1 to 2 billion to find a number that is the answer.

Computing the middle with just `/ 2`JavaScript · TypeScript

const a = [10, 20, 30];
let lo = 0, hi = a.length;
while (lo < hi) {
  const mid = (lo + hi) / 2;
  if (a[mid] < 25) lo = mid + 1;
  else hi = mid;
}
console.log(lo);

→ 1 — the answer is 2. The first mid is 1.5 and a[1.5] is undefined with no error, so after 1,077 laps it hands back the wrong position

Round down with Math.floor((lo + hi) / 2).
Then it prints 2.

How languages differ
Binary search is correct only on a sorted list.
Looking for 30 in the unsorted [30, 10, 20] with bisect_left gives 3 (meaning "not there") with no error.
The starting values matter by one, too: if the example started hi at n - 1 instead of n, then searching [10, 20, 30] for 99, which is larger than everything, would give 2 instead of 3.

Binary Search

Key points

How each language writes it

Common mistakes

Narrowing with lo = mid never ends

(lo + hi) / 2 overflowedJava · C# · C · C++

Computing the middle with just / 2JavaScript · TypeScript

Practice

Narrowing with `lo = mid` never ends

`(lo + hi) / 2` overflowedJava · C# · C · C++

Computing the middle with just `/ 2`JavaScript · TypeScript