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

CSA | animation, code, lower_bound + upper_bound | ||

CPH | code, lower_bound + upper_bound, some applications | ||

CF | problems similar to those covered in this module | ||

KA | plenty 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 | |||
---|---|---|---|

CPP | with examples |

Java

Resources | |||
---|---|---|---|

JAVA | |||

JAVA |

Python

Resources | |||
---|---|---|---|

Python | |||

GFG |

## 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{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 bisectinp = 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.