PrevNext

You're not signed in!

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

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

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 the lower_bound and upper_bound functions given above to count the number of cows in any range [A,B][A,B] in O(logN)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_back
8#define rsz resize
9#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 IOException
6 {
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.

Module Progress:

Give Us Feedback on Binary Search on a Sorted Array!

PrevNext