Not Frequent
0/1

# Binary Search on a Sorted Array

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

### Prerequisites

Quickly finding elements in a sorted array.

Suppose that we want to find an element in a sorted array of size $N$ in $\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 $\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.

C++

Resources
CPPwith examples

## Example - Counting Haybales

Focus Problem – read through this problem before continuing!

As each of the points are in the range $0 \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]$ in $\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
{
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("haybales.out")));
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')
for i in range(Q):
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.

### 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.