Course navigation & on this page
Binary search timing experiment
Study logarithmic queries while separating preprocessing and I/O from the measured run.
Overview
Study logarithmic queries while separating preprocessing and I/O from the measured run. The search interval halves at each unsuccessful inspection. The experiment’s full elapsed time includes more than indexOf, so compare equivalent inputs and account for reading, sorting and printing.
Step-by-step walkthrough
- Read and sort the allowlist in main.
- Use lo and hi to delimit candidate indices.
- Inspect the middle and eliminate one half.
- Return the matching index or −1; the client prints keys absent from the allowlist.
Complexity analysis
| Best case | Θ(1) per query |
|---|---|
| Average / aggregate | Θ(log n) under uniform successful positions |
| Worst case | Θ(log n) per query |
| Space | Θ(1) query auxiliary space |
The search interval halves at each unsuccessful inspection. The experiment’s full elapsed time includes more than indexOf, so compare equivalent inputs and account for reading, sorting and printing.
A worked example
With 1024 sorted items, the maximum number of middle inspections is at most 11 for the usual inclusive interval.
Common mistake / implementation note
Do not attribute all measured milliseconds to binary search. Short timings are also sensitive to timer resolution and runtime warm-up.
Do not attribute all measured milliseconds to binary search. Short timings are also sensitive to timer resolution and runtime warm-up.
Original course code
Source: code/BinarySearchTime.java. Original logic, comments, variable names and attribution are retained.
Download BinarySearchTime.javaBinarySearchTime.javaJAVA
/****************************************************************************** * Compilation: javac BinarySearch.java * Execution: java BinarySearch allowlist.txt < input.txt * Dependencies: In.java StdIn.java StdOut.java * Data files: https://algs4.cs.princeton.edu/11model/tinyW.txt * https://algs4.cs.princeton.edu/11model/tinyT.txt * https://algs4.cs.princeton.edu/11model/largeW.txt * https://algs4.cs.princeton.edu/11model/largeT.txt * * % java BinarySearch tinyAllow.txt < tinyT.txt * 50 * 99 * 13 * * % java BinarySearch largeAllow.txt < largeT.txt | more * 499569 * 984875 * 295754 * 207807 * 140925 * 161828 * [367,966 total values] * ******************************************************************************/ //package edu.princeton.cs.algs4; import java.util.Arrays;import java.io.*; /** * The {@code BinarySearch} class provides a static method for binary * searching for an integer in a sorted array of integers. * <p> * The <em>indexOf</em> operations takes logarithmic time in the worst case. * <p> * For additional documentation, see <a href="https://algs4.cs.princeton.edu/11model">Section 1.1</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */public class BinarySearchTime { /** * This class should not be instantiated. */ private BinarySearchTime() { } /** * Returns the index of the specified key in the specified array. * * @param a the array of integers, must be sorted in ascending order * @param key the search key * @return index of key in array {@code a} if present; {@code -1} otherwise */ public static int indexOf(int[] a, int key) { int lo = 0; int hi = a.length - 1; while (lo <= hi) { // Key is in a[lo..hi] or not present. int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else return mid; } return -1; } /** * Returns the index of the specified key in the specified array. * This function is poorly named because it does not give the <em>rank</em> * if the array has duplicate keys or if the key is not in the array. * * @param key the search key * @param a the array of integers, must be sorted in ascending order * @return index of key in array {@code a} if present; {@code -1} otherwise * @deprecated Replaced by {@link #indexOf(int[], int)}. */ @Deprecated public static int rank(int key, int[] a) { return indexOf(a, key); } /** * Reads in a sequence of integers from the allowlist file, specified as * a command-line argument; reads in integers from standard input; * prints to standard output those integers that do <em>not</em> appear in the file. * * @param args the command-line arguments */ public static void main(String[] args) { long start = System.currentTimeMillis(); // read the integers from a file In in = new In(args[0]); int[] allowlist = in.readAllInts(); // sort the array Arrays.sort(allowlist); // read integer key from standard input; print if not in allowlist while (!StdIn.isEmpty()) { int key = StdIn.readInt(); if (BinarySearchTime.indexOf(allowlist, key) == -1) StdOut.println(key); } long end = System.currentTimeMillis(); System.out.println("Total time taken: " + (end - start) + "ms"); }} /****************************************************************************** * Copyright 2002-2020, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/