Binary Search on 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.

Library Functions

Example - Counting Haybales

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.

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

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

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(new BufferedWriter(new FileWriter("haybales.out")));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());

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