8. Binary Search

🧸 ELI5: You're playing a guessing game: "I'm thinking of a number between 1 and 100." Instead of guessing 1, 2, 3, 4... you guess 50 (the middle). Too high? Now you know it's between 1-49, so you guess 25. Too low? Now you know it's between 26-49, so you guess... You cut the possibilities in half every single time.

🌍 Real life: Looking up a word in a paper dictionary — you don't start at "A," you flip to the middle, see you're past your word, flip back halfway, and narrow in. This only works if the list is already sorted.

📝 Pseudocode:

function binarySearch(sortedList, target):
    low = 0
    high = length(sortedList) - 1
    while low <= high:
        mid = (low + high) / 2
        if sortedList[mid] == target:
            return mid
        else if sortedList[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

🐹 Go:

package main

import "fmt"

func binarySearch(sorted []int, target int) int {
	low, high := 0, len(sorted)-1
	for low <= high {
		mid := (low + high) / 2
		switch {
		case sorted[mid] == target:
			return mid
		case sorted[mid] < target:
			low = mid + 1
		default:
			high = mid - 1
		}
	}
	return -1
}

func main() {
	pages := []int{2, 8, 15, 23, 42, 71, 99}
	fmt.Println(binarySearch(pages, 42)) // 4
}

🇨 C:

#include <stdio.h>

int binary_search(const int *sorted, int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // avoids (low+high) overflowing for huge arrays
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main(void) {
    int pages[] = {2, 8, 15, 23, 42, 71, 99};
    printf("%d\n", binary_search(pages, 7, 42)); // 4
    return 0;
}

⏱️ Complexity: O(log n) — doubling the toy box size only adds one more guess. 1,000,000 items? Just ~20 guesses.