Skip to main content
Engineering LibreTexts

3.8: Binary Search

  • Page ID
    20804
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    When you look for a word in a dictionary, you don’t just search page by page from front to back. Since the words are in alphabetical order, you probably use a binary search algorithm:

    1. Start on a page near the middle of the dictionary.
    2. Compare a word on the page to the word you are looking for. If you find it, stop.
    3. If the word on the page comes before the word you are looking for, flip to somewhere later in the dictionary and go to step 2.
    4. If the word on the page comes after the word you are looking for, flip to somewhere earlier in the dictionary and go to step 2.

    If you find two adjacent words on the page and your word comes between them, you can conclude that your word is not in the dictionary.

    Getting back to the array of cards, we can write a faster version of search if we know the cards are in order:

    public static int binarySearch(Card[] cards, Card target) {
        int low = 0;
        int high = cards.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;                 // step 1
            int comp = cards[mid].compareTo(target);
    
            if (comp == 0) {                            // step 2
                return mid;
            } else if (comp < 0) {                      // step 3
                low = mid + 1;
            } else {                                    // step 4
                high = mid - 1;
            }
        }
        return -1;
    }
    

    First, we declare low and high variables to represent the range we are searching. Initially we search the entire array, from 0 to length - 1.

    Inside the while loop, we repeat the four steps of binary search:

    1. Choose an index between low and high – call it mid – and compare the card at mid to the target.
    2. If you found the target, return the index.
    3. If the card at mid is lower than the target, search the range from mid + 1 to high.
    4. If the card at mid is higher than the target, search the range from low to mid - 1.

    If low exceeds high, there are no cards in the range, so we break out of the loop and return -1. Notice that this algorithm depends on the compareTo method of the object.


    This page titled 3.8: Binary Search is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?