PrevNext
Not Frequent
 0/1

Binary Search on a Sorted Array

Authors: Siyong Huang, Michael Cao, Nathan Chen, Andrew Wang

Quickly finding elements in a sorted array.

Suppose that we want to find an element in a sorted array of size NN in O(logN)\mathcal{O}(\log N) time. We can do this with binary search; each iteration of the binary search cuts the search space in half, so the algorithm tests O(logN)\mathcal{O}(\log N) values. This is efficient and much better than testing every element in an array.

Resources
CSAanimation, code, lower_bound + upper_bound
CPHcode, lower_bound + upper_bound, some applications
CFproblems similar to those covered in this module
KAplenty of diagrams, javascript implementation

Warning!

The code provided in the CSAcademy link under "Binary search on functions" is not correct! See Binary Search on the Answer for details.

Library Functions

C++

Resources
CPPwith examples

Example - Counting Haybales

Focus Problem – read through this problem before continuing!

As each of the points are in the range 01,000,000,0000 \ldots 1,000,000,000, storing locations of haybales in a boolean array and then taking prefix sums of that would take too much time and memory.

Instead, let's place all of the locations of the haybales into a list and sort it. Now we can use binary search to count the number of cows in any range [A,B][A,B] in O(logN)\mathcal{O}(\log N) time.

C++

We can use the the builtin lower_bound and upper_bound functions.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

Java

We can use the builtin Arrays.binarySearch function.

import java.io.*;
import java.util.*;
public class haybales{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new FileReader(new File("haybales.in")));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("haybales.out")));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());

Python

We can use the builtin bisect.bisect function.

from bisect import bisect
inp = open("haybales.in", 'r')
out = open("haybales.out", 'w')
N, Q = map(int, inp.readline().split())
arr = sorted(list(map(int, inp.readline().split())))
for i in range(Q):
a, b = map(int, inp.readline().split())
print(bisect(arr, b) - bisect(arr, a-1), file=out)
inp.close()
out.close()

Of course, the official solution does not use a library implementation of binary search.

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Binary Search on a Sorted Array!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext