typestar

Binary search in Go

Halve the range each step; a thousand items takes ten comparisons.

func binarySearch(items []int, target int) int {
    lo, hi := 0, len(items)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        if items[mid] == target {
            return mid
        }
        if items[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

Keywords and builtins used here

The run, in numbers

Lines
15
Characters to type
225
Tokens
77
Three-star pace
90 tpm

At the three-star pace of 90 tokens a minute, this run takes about 51 seconds.

Type this snippet

Step 8 of 9 in Arrays, slices & maps, step 23 of 30 in Language basics.

← Previous Next →

Binary search in other languages