Skip to content
Go: Find the first sorted value that meets a threshold

Go: Find the first sorted value that meets a threshold

November 14, 2026

A sorted capacity table can answer which entry first meets a requested size. sort.Search finds the first true result of a predicate, including the boundary before duplicate values. Its return value may also be past the last entry.

Set up

Tested on Linux amd64 with Go 1.26.10. Use Bash with Go on your PATH, a text editor, and the mktemp, rm, and rmdir utilities. The example uses only the standard library. Keep the same terminal through cleanup, and stop if setup fails before saving the source.

start_dir="$PWD"
work_dir="$(mktemp -d)" || exit 1
cd -- "$work_dir" || exit 1

Run the example

Save as go-sort-search-first-threshold.go:

package main

import (
	"fmt"
	"sort"
)

func firstAtLeast(values []int, target int) int {
	return sort.Search(len(values), func(i int) bool { return values[i] >= target })
}

func main() {
	capacities := []int{8, 16, 16, 32}
	for _, target := range []int{0, 16, 17, 40} {
		i := firstAtLeast(capacities, target)
		fmt.Printf("target=%d index=%d", target, i)
		if i < len(capacities) {
			fmt.Printf(" capacity=%d", capacities[i])
		}
		fmt.Println()
	}
	if firstAtLeast(capacities, 16) != 1 {
		panic("duplicate boundary")
	}
	if firstAtLeast(capacities, 40) != len(capacities) {
		panic("missing boundary")
	}
	if firstAtLeast(nil, 1) != 0 {
		panic("empty boundary")
	}
	fmt.Println("empty index:", firstAtLeast(nil, 1))
}

Run:

go run go-sort-search-first-threshold.go

Observed output:

target=0 index=0 capacity=8
target=16 index=1 capacity=16
target=17 index=3 capacity=32
target=40 index=4
empty index: 0

Read the result

For an ascending slice, the predicate is false below the threshold and true at or above it. The first matching duplicate is therefore the boundary returned for the exact threshold. The no-match result equals the slice length, so the program checks that boundary before indexing.

An empty slice returns zero without invoking the predicate. The search does not rearrange or validate the input; the caller supplies the ordered data.

Apply it carefully

The predicate must remain false and then true as indices increase. An unsorted table or a predicate that changes during the search breaks that contract. Keep the slice stable while searching. Finding an equal value requires an additional equality check at the returned index; finding a sufficient capacity only needs the threshold test used here. The algorithm uses logarithmically many predicate calls, but any work performed inside the predicate still contributes to the cost.

See the Go standard-library reference.

Clean up

Remove the saved source and the empty scratch directory. Go manages its build cache separately. If the directory is not empty, inspect its contents before removing anything else.

rm -- go-sort-search-first-threshold.go
cd -- "$start_dir" || exit 1
rmdir -- "$work_dir"
unset start_dir work_dir

Acknowledgements

This post was created with assistance from AI.

Last updated on