Algorithms

Binary Search

Binary search finds a value in a sorted list by checking the middle and throwing away the half it cannot be in, over and over.

Strategy

Decrease and conquer

Every comparison rules out half of what is left.

Halve: look at the middle value of the stretch still in play.
Discard: drop the half the target cannot be in.
Repeat: search the half that remains the same way.

active range comparing eliminated found

Press Step to check one middle value at a time. Whichever way the comparison goes, half the remaining range disappears.

Purpose

Find where a value sits in a sorted list.

Input

A sorted []int and the int to look for.

Output

The index of the value, or -1 when the list does not hold it.

Constraints

The list has to be sorted before the first call.
With duplicate values you get one of the matching indexes, and which one depends on the list.
Take the midpoint as low + (high-low)/2, since (low+high)/2 can overflow on a huge slice.

How binary search works

Think of looking up a word in a dictionary. You do not start at page one. You open somewhere in the middle, see whether your word comes before or after, and throw away the half it cannot be in. Then you do it again with what is left.

Throwing away half each time is why it is so quick. A thousand values take about ten checks. The catch is that the list has to be sorted first.

What binary search keeps track of

Name	Type	What it is for
arr	[]int	The values to search. They have to be in order already.
target	int	The value you are looking for.
low	int	First index still worth checking.
high	int	Last index still worth checking.
mid	int	The middle of what is left, and the value you compare.

Walk through it

1 Start with a sorted list and something to find

Mark the whole list as the part still worth searching.

arr := []int{4, 11, 19, 27, 34, 42, 50, 58, 66}
target := 58

low, high := 0, len(arr)-1

2 Look at the middle value

Find the index halfway between the two markers. Writing it this way instead of adding low and high keeps the sum from overflowing on a huge slice.

mid := low + (high-low)/2

3 Compare it to your target

Three things can happen. You found it, or the middle is too small, or it is too big.

switch {
case arr[mid] == target:
    return mid
case arr[mid] < target:
    low = mid + 1  // too small, look right
default:
    high = mid - 1 // too big, look left
}

4 Repeat on whatever is left

Each pass moves one marker past the middle, so the gap between them shrinks by half.

for low <= high {
    // pick the middle, compare, move a marker
}

5 Stop when the markers cross

If the markers pass each other there is nothing left to check, so the value is not in the list.

return -1

The whole program

Put it together and you get the index of the value, or -1 when it is not there.

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1

    for low <= high {
        mid := low + (high-low)/2

        switch {
        case arr[mid] == target:
            return mid
        case arr[mid] < target:
            low = mid + 1
        default:
            high = mid - 1
        }
    }
    return -1
}

func main() {
    arr := []int{4, 11, 19, 27, 34, 42, 50, 58, 66}

    fmt.Println(binarySearch(arr, 58))
    fmt.Println(binarySearch(arr, 40))
}

Terminal

$ go run main.go
7
-1

Previous Quick Sort Next Topic Merge Sort