### You're not signed in!

Sign in to save your progress and sync your settings across devices.

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

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

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

KA | plenty of diagrams, javascript implementation |

## Library Functions

C++

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

CPP | with examples |

Java

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

JAVA | |||

JAVA |

## 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;34using ll = long long;56using 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.*;34public 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.