Binary Search — Programuoki

Code

The boundaries — this is where it breaks

Create search_test.go (see the panel). We write this test; your job is to make LowerBound pass it.

The happy path — "the item is somewhere in the middle" — is easy. Every case below is where a hand-rolled binary search actually breaks.

Ten boundary cases

$ go test -run TestLowerBoundBoundaries -v .
=== RUN   TestLowerBoundBoundaries/exact_match,_first
=== RUN   TestLowerBoundBoundaries/exact_match,_middle
=== RUN   TestLowerBoundBoundaries/exact_match,_last
=== RUN   TestLowerBoundBoundaries/between_two_items
=== RUN   TestLowerBoundBoundaries/before_everything
=== RUN   TestLowerBoundBoundaries/AFTER_everything
=== RUN   TestLowerBoundBoundaries/empty_slice
=== RUN   TestLowerBoundBoundaries/single_item,_before
=== RUN   TestLowerBoundBoundaries/single_item,_exact
=== RUN   TestLowerBoundBoundaries/single_item,_after
--- PASS: TestLowerBoundBoundaries (0.00s)

Three of them deserve their own paragraph.

"AFTER everything" returns 4 for a 4-item library. An index that does not exist. That is exactly why hi starts at len(items) and not len(items)-1: the answer "past the end" needs somewhere to live. Start at len-1 and this case silently returns the last item instead.

An empty slice returns 0 and never enters the loop, because lo < hi is false immediately. The zero case takes care of itself — if the invariant is right.

A one-item library is checked three times, because mid is always 0 there and a mistake with mid + 1 turns into an infinite loop.

Duplicates: which of the three?

lib := sorted("a", "b", "b", "b", "c")
LowerBound(lib, "b")  // → 1

Three "b"s. The correct answer is the first, index 1. That is what lower bound means.

If your search returns 2 or 3 it looks right and will survive a casual check. But code that scans forward from the result to collect every match will miss some of them — and the bug will surface somewhere else entirely.

transit tests its search semantics rather than assuming them, for the same reason.

And the most important test

$ go test -run TestUnsortedInputSilentlyLies -v .
    search_test.go:93: unsorted input: linear says 0, binary says 2 —
                       binary is wrong, and silent

Unsorted input is not an error to a binary search. It reports nothing. It simply returns the wrong number.

Gotcha

Sorted order is a precondition, not a recommendation. Linear search always works; binary search works only when its condition holds, and it does not check — checking would cost O(n) and destroy the entire point. Preconditions are your program's job to protect, not the search's.

search_test.go CREATE

Create this file in ./

package main

import (
	"fmt"
	"testing"

	"algo/metrics"
)

// sorted builds a sorted library from the titles given, in order.
func sorted(titles ...string) []Item {
	items := make([]Item, len(titles))
	for i, t := range titles {
		items[i] = Item{ID: i + 1, Title: t}
	}
	return items
}

// THE BOUNDARIES ARE THE LESSON. A binary search that works on "the item is
// somewhere in the middle" is easy. Every one of these cases is where a
// hand-rolled one actually breaks.
func TestLowerBoundBoundaries(t *testing.T) {
	lib := sorted("b", "d", "f", "h")
	cases := []struct {
		name   string
		items  []Item
		target string
		want   int
	}{
		{"exact match, first", lib, "b", 0},
		{"exact match, middle", lib, "f", 2},
		{"exact match, last", lib, "h", 3},
		{"between two items", lib, "e", 2},
		{"before everything", lib, "a", 0},
		{"AFTER everything", lib, "z", 4}, // len(items) — one past the end
		{"empty slice", nil, "a", 0},
		{"single item, before", sorted("m"), "a", 0},
		{"single item, exact", sorted("m"), "m", 0},
		{"single item, after", sorted("m"), "z", 1},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			var c metrics.Counter
			if got := LowerBound(tc.items, tc.target, &c); got != tc.want {
				t.Errorf("LowerBound(%q) = %d, want %d", tc.target, got, tc.want)
			}
		})
	}
}

// With duplicates there is more than one correct-looking answer. LOWER BOUND
// is defined to land on the FIRST. If yours lands on any of them, it is not a
// lower bound — and code that scans forward from the result will miss rows.
func TestLowerBoundLandsOnTheFirstDuplicate(t *testing.T) {
	lib := sorted("a", "b", "b", "b", "c")
	var c metrics.Counter
	got := LowerBound(lib, "b", &c)
	if got != 1 {
		t.Fatalf("LowerBound(\"b\") = %d, want 1 (the FIRST of three)", got)
	}
}

// The three searches must agree everywhere, or comparing their speed is
// meaningless. This is the same discipline transit uses before benchmarking:
// prove they are the same function first.
func TestAllThreeAgree(t *testing.T) {
	lib := make([]Item, 0, 200)
	for i := 0; i < 200; i++ {
		lib = append(lib, Item{ID: i, Title: fmt.Sprintf("%04d", i*3)})
	}
	for probe := 0; probe < 620; probe++ {
		target := fmt.Sprintf("%04d", probe)
		var c1, c2, c3 metrics.Counter
		a := LinearAtOrAfter(lib, target, &c1)
		b := LowerBound(lib, target, &c2)
		d := LowerBoundStd(lib, target, &c3)
		if a != b || b != d {
			t.Fatalf("target %q: linear=%d hand=%d std=%d", target, a, b, d)
		}
	}
}

// A sorted input is a PRECONDITION, not a suggestion. On unsorted data binary
// search does not error — it silently returns a wrong answer.
func TestUnsortedInputSilentlyLies(t *testing.T) {
	lib := sorted("f", "b", "h", "d") // NOT sorted
	var c1, c2 metrics.Counter
	linear := LinearAtOrAfter(lib, "d", &c1)
	binary := LowerBound(lib, "d", &c2)
	if linear == binary {
		t.Skip("this input happened not to expose the difference")
	}
	t.Logf("unsorted input: linear says %d, binary says %d — binary is wrong, and silent", linear, binary)
}