Course navigation & on this page
Binary search
Locate a key in a sorted array by halving the candidate interval.
Overview
Locate a key in a sorted array by halving the candidate interval. Each unsuccessful middle comparison removes at least half the remaining candidates. After about log₂ n halvings, at most one remains. Sorting in main is separate from indexOf’s query cost.
Step-by-step walkthrough
- Initialize lo = 0 and hi = a.length − 1.
- Compute mid = lo + (hi − lo) / 2.
- For a smaller key, set hi = mid − 1; for a larger key, set lo = mid + 1.
- Return mid on equality; return −1 after the interval becomes empty.
Complexity analysis
| Best case | Θ(1) |
|---|---|
| Average / aggregate | Θ(log n) under a uniform successful-key model |
| Worst case | Θ(log n) |
| Space | Θ(1) auxiliary |
Each unsuccessful middle comparison removes at least half the remaining candidates. After about log₂ n halvings, at most one remains. Sorting in main is separate from indexOf’s query cost.
A worked example
Search for 43 in [6, 13, 14, 25, 33, 43, 51]: inspect 25, then 43. Return index 5.
Interactive dry run
Follow the search interval
6131425334351
Step 1 of 2: 25 < 43: discard indices 0 through 3.
Common mistake / implementation note
Searching an unsorted array invalidates the elimination rule. Duplicate keys may return any matching index, not necessarily the first.
Searching an unsorted array invalidates the elimination rule. Duplicate keys may return any matching index, not necessarily the first.
Original course code
Source: code/BinarySearch.java. Original logic, comments, variable names and attribution are retained.
Download BinarySearch.javaBinarySearch.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; /** * 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 BinarySearch { /** * This class should not be instantiated. */ private BinarySearch() { } /** * 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) { // 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 (BinarySearch.indexOf(allowlist, key) == -1) StdOut.println(key); } }} /****************************************************************************** * 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. ******************************************************************************/