PrevNext
Somewhat Frequent
 0/3

Binary Search on a Sorted Array

Authors: Darren Yao, Abutalib Namazov, Andrew Wang, Qi Wang, Dustin Miao

Efficiently searching for a value in a sorted array.

Edit This Page

Binary Search on a Sorted Array

C++

Resources
CPP
lower_bound, upper_bound

with examples

Please check the Binary Search module for additional resources (though they cover additional material not part of this module).

Example - Counting Haybales

Counting Haybales
Silver - Easy

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

As each of the points are in the range 0…1 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 binary search to count both the number of haybales with position at most BB and the number of haybales with position less than AA in O(log⁡N)\mathcal{O}(\log N) time, and then subtract these two quantities to get the final answer.

Without Built-in Functions

C++

#include <bits/stdc++.h>
using namespace std;


void setIO(string name = "") {  // name is nonempty for USACO file I/O
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // see Fast Input & Output
	// alternatively, cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);  // see Input & Output
		freopen((name + ".out").c_str(), "w", stdout);

Java

import java.io.*;
import java.util.*;


public class Haybales {
	static int[] bales;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("haybales");
		int baleNum = io.nextInt();
		int queryNum = io.nextInt();
		bales = new int[baleNum];

Python

def at_most(x: int) -> int:
	lo = 0
	hi = len(bales)
	while lo < hi:
		mid = (lo + hi) // 2
		if bales[mid] <= x:
			lo = mid + 1
		else:
			hi = mid
	return lo

With Built-in Functions

C++

We can use the the built-in lower_bound and upper_bound functions.

#include <bits/stdc++.h>
using namespace std;


void setIO(string name = "") {  // name is nonempty for USACO file I/O
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // see Fast Input & Output
	// alternatively, cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);  // see Input & Output
		freopen((name + ".out").c_str(), "w", stdout);

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("haybales.out");
		StringTokenizer st = new StringTokenizer(br.readLine());


		int baleNum = Integer.parseInt(st.nextToken());

Python

We can use the builtin bisect.bisect function.

from bisect import bisect


inp = open("haybales.in", "r")
out = open("haybales.out", "w")


bale_num, query_num = map(int, inp.readline().split())
bales = sorted(list(map(int, inp.readline().split())))
for _ in range(query_num):
	start, end = map(int, inp.readline().split())
	print(bisect(bales, end) - bisect(bales, start - 1), file=out)

Problems

StatusSourceProblem NameDifficultyTags
CF
Cellular Network
Easy
Show Tags2P, Binary Search
Silver
Cow-libi
Easy
Show TagsBinary 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
PrevNext