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.

Library FunctionsExample - Counting Haybales
Edit on Github

Suppose that we want to find an element in a sorted array of size $N$ in $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(\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
KAplenty of diagrams, javascript implementation

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 the lower_bound and upper_bound functions given above to count the number of cows in any range $[A,B]$ in $O(\log N)$ time.

C++

1#include <bits/stdc++.h>2using namespace std;3
4using ll = long long;5
6using vi = vector<int>;7#define pb push_back8#define rsz resize9#define all(x) begin(x), end(x)10#define sz(x) (int)(x).size()

Java

1import java.io.*; 2import java.util.*; 3
4public class haybales{5   public static void main(String[] args) throws IOException6   {7      BufferedReader br = new BufferedReader(new FileReader(new File("haybales.in")));8      PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("haybales.out")));9      StringTokenizer st = new StringTokenizer(br.readLine());10      int N = Integer.parseInt(st.nextToken());

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