PrevNext
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 in time. We can do this with binary search; each iteration of the binary search cuts the search space in half, so the algorithm tests values. This is efficient and much better than testing every element in an array.

Resources
CSA
Binary Search
animation, code, lower_bound + upper_bound
CPH
3.3 - Binary Search
code, lower_bound + upper_bound, some applications
CF
EDU: Binary Search - Step 1
problems similar to those covered in this module
KA
Binary Search
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
lower_bound, upper_bound
with examples

Example - Counting Haybales

Counting Haybales

Silver - Easy

Focus Problem – read through this problem before continuing!

As each of the points are in the range , 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 in time.

C++

We can use the the builtin lower_bound and upper_bound functions.

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

We can use the builtin Arrays.binarySearch function.

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

Python

We can use the builtin bisect.bisect function.

1from bisect import bisect
2

3inp = open("haybales.in", 'r')
4out = open("haybales.out", 'w')
5

6N, Q = map(int, inp.readline().split())
7arr = sorted(list(map(int, inp.readline().split())))
8

9for i in range(Q):
10    a, b = map(int, inp.readline().split())

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!

Join Forum

Give Us Feedback on Binary Search on a Sorted Array!

PrevNext