Binary Search

Iterative binary search over a sorted sequence, O(log n) time. Same logic in three languages so I can grab whichever one matches the project I'm in.

binary_search.py

def binary_search(items, target):
    """Return the index of target in a sorted list, or -1 if absent."""
    low, high = 0, len(items) - 1

    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1


if __name__ == "__main__":
    values = [1, 3, 4, 7, 9, 12, 18, 21]
    print(binary_search(values, 12))  # 5

binarySearch.js

function binarySearch(items, target) {
  let low = 0;
  let high = items.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (items[mid] === target) {
      return mid;
    } else if (items[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

const values = [1, 3, 4, 7, 9, 12, 18, 21];
console.log(binarySearch(values, 12)); // 5

binary_search.go

package main

import "fmt"

func binarySearch(items []int, target int) int {
	low, high := 0, len(items)-1

	for low <= high {
		mid := low + (high-low)/2
		switch {
		case items[mid] == target:
			return mid
		case items[mid] < target:
			low = mid + 1
		default:
			high = mid - 1
		}
	}
	return -1
}

func main() {
	values := []int{1, 3, 4, 7, 9, 12, 18, 21}
	fmt.Println(binarySearch(values, 12)) // 5
}

All three keep the same shape: track a low and high bound, check the midpoint, and narrow the range until the target is found or the bounds cross. Go's version uses low + (high-low)/2 instead of (low + high) / 2 to avoid integer overflow on very large slices.