Sorting and Searching

The problem

500,000 bars in time order. "What was the price at 14:30 on the third of March?" Scanning all of them works. Doing it a thousand times during a backtest doesn't.

Sorting

import "sort"

prices := []float64{102.5, 99.8, 101.2, 100.5}
sort.Float64s(prices)
fmt.Println(prices)        // [99.8 100.5 101.2 102.5]

sort.Ints and sort.Strings exist too. For anything else, sort.Slice takes a function saying whether element i comes before element j:

sort.Slice(trades, func(i, j int) bool {
	return trades[i].Entry.Timestamp.Before(trades[j].Entry.Timestamp)
})

Sort by P&L, largest first:

sort.Slice(trades, func(i, j int) bool {
	return trades[i].PnL() > trades[j].PnL()
})

Go 1.21 added a slices package with a cleaner form, where the comparison returns negative, zero, or positive:

import "slices"

slices.SortFunc(trades, func(a, b Trade) int {
	return a.Entry.Timestamp.Compare(b.Entry.Timestamp)
})

Either is fine. slices is newer and reads better.

Stability

An unstable sort may reorder equal elements. sort.Slice is unstable; sort.SliceStable isn't.

It matters when you sort by one key and want a previous ordering preserved among ties - sorting trades by symbol while keeping each symbol's trades in time order, for instance. Stability costs a little performance and buys predictability.

Binary search: the actual idea

Sorting is a means to an end, and the end is fast lookup.

To find a value in sorted data: look at the middle. Too high? Everything from the middle up is irrelevant - throw away half. Too low? Throw away the other half. Repeat.

Each step halves the remaining range. For a million elements, that's about 20 steps, because 2²⁰ is a bit over a million. Twenty comparisons instead of a million.

   searching for 42 in a sorted list of 16
   ┌───────────────────────────────────────┐
   │ 3 8 12 19 25 31 38 42 49 55 61 70 ... │   check middle (49) → too high
   └───────────────────────────────────────┘
   ┌───────────────────┐
   │ 3 8 12 19 25 31 38 42 │                   check middle (25) → too low
   └───────────────────┘
                     ┌───────┐
                     │ 31 38 42 │               check middle (38) → too low
                     └───────┘
                            ┌────┐
                            │ 42 │              found
                            └────┘

See It Work: watch it halve

Write it yourself with the probes printed, and the idea stops being abstract:

func binarySearchVerbose(prices []float64, target float64) int {
	low, high := 0, len(prices)-1
	step := 0

	for low <= high {
		mid := low + (high-low)/2
		step++
		fmt.Printf("step %2d: range [%d..%d] (%d left), probing index %d = %.2f\n",
			step, low, high, high-low+1, mid, prices[mid])

		switch {
		case prices[mid] == target:
			fmt.Printf("found after %d steps\n", step)
			return mid
		case prices[mid] < target:
			low = mid + 1
		default:
			high = mid - 1
		}
	}
	fmt.Printf("not found after %d steps\n", step)
	return -1
}

Run it on a sorted slice of 1,000,000 and watch:

step  1: range [0..999999] (1000000 left), probing index 499999 = ...
step  2: range [500000..999999] (500000 left), ...
step  3: range [750000..999999] (250000 left), ...
...
step 20: range [999998..999999] (2 left), ...
found after 20 steps

A million down to twenty. The "left" column halving every line is O(log n) made visible.

Note mid := low + (high-low)/2 rather than (low+high)/2. Both are correct here; the first avoids integer overflow when the indices are enormous. It's a famous bug - binary search implementations shipped with it for years - and it's free to avoid.

See It Work: count the comparisons

func BenchmarkLinearSearch(b *testing.B) {
	data := sortedData(1_000_000)
	target := data[999_999]
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, v := range data {
			if v == target { break }
		}
	}
}

func BenchmarkBinarySearch(b *testing.B) {
	data := sortedData(1_000_000)
	target := data[999_999]
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sort.SearchFloat64s(data, target)
	}
}

Expect a difference around five orders of magnitude. Then re-run both at 1,000 elements: linear gets a thousand times faster, binary gets about 30% faster. Binary search barely notices the problem getting bigger. That's the property you're buying.

Using the standard library

You rarely write binary search by hand. sort.Search finds the smallest index where a condition first becomes true:

// First bar at or after a target time.
idx := sort.Search(len(bars), func(i int) bool {
	return !bars[i].Timestamp.Before(target)
})

if idx < len(bars) {
	fmt.Println("first bar at or after target:", bars[idx])
} else {
	fmt.Println("target is after all bars")
}

That "smallest index where true" formulation is more useful than exact-match search, because market data rarely has a bar at precisely the timestamp you asked for. You want the next one.

slices.BinarySearchFunc is the newer equivalent and returns the index plus whether it was an exact match.

The trap

Binary search on unsorted data doesn't error - it returns nonsense. There's no check; sortedness is your responsibility. Sort first, or maintain the ordering as you insert.

Exercises

12.1 Sort a slice of trades by P&L descending and print the best five and worst five.

12.2 Implement binarySearchVerbose and run it on 1,000, 100,000 and 10,000,000 elements. Record the step counts. Do they match log₂(n)?

12.3 Write barAt(bars []Bar, t time.Time) (Bar, bool) returning the last bar at or before t. Careful with the boundaries - a target before the first bar has no answer.

12.4 Benchmark linear versus binary search at 1,000 / 100,000 / 10,000,000 elements. Tabulate and describe the shape of each curve.

12.5 Write percentile(values []float64, p float64) float64 returning the p-th percentile. Sort a copy, don't mutate the caller's slice. Use it to find the 5th percentile of daily returns from prices.csv - a crude value-at-risk.

12.6 Harder. Given trades sorted by entry time, write overlapping(trades []Trade) [][2]int finding all pairs whose holding periods overlap. The naive version is O(n²); use the sortedness to do better.

Solutions

12.2 10, 17 and 24 steps respectively - exactly ⌈log₂(n)⌉. Multiplying the data by 10,000 adds about 13 steps.

12.3

func barAt(bars []Bar, t time.Time) (Bar, bool) {
	idx := sort.Search(len(bars), func(i int) bool {
		return bars[i].Timestamp.After(t)
	})
	if idx == 0 {
		return Bar{}, false      // t is before every bar
	}
	return bars[idx-1], true
}

Search finds the first bar strictly after t, so the one before it is the last at or before. Getting this off by one is easy - write a test.

12.5

func percentile(values []float64, p float64) float64 {
	if len(values) == 0 { return 0 }
	sorted := make([]float64, len(values))
	copy(sorted, values)
	sort.Float64s(sorted)

	idx := int(p / 100 * float64(len(sorted)-1))
	return sorted[idx]
}

The copy matters: silently reordering the caller's data is exactly the Chapter 7 sharing trap.

12.6 Sort by entry time (already done), then sweep once keeping a list of trades still open at the current time, discarding those that have exited. That's O(n log n) plus the number of overlaps you actually report.