viz_binary_search.py

import sys
from operator import gt, ge

cmp = ge

def search(a, x):
	print('search:', x)
	i, j = 0, len(a)
	while i < j:
		h = (i+j) // 2
		show(a,i,j)
		# if a[h] >= x: # bisect_left
		# if a[h] > x: # bisect_right
		if cmp(a[h], x):
			j = h
		else:
			i = h + 1
	show(a,i,j)
	def get(i):
		try:
			return a[i]
		except:
			return float('inf')
	assert i == j
	print('got:', get(i))
	print()

def show(a, i, j):
	h = (i+j) // 2
	print(*a[:i], '[', *a[i:h], '/', *a[h:j], ']', *a[j:])

def repl():
	1/0 # TODO

# Python3.10+ needed
match sys.argv:
	case [_, n, x]:
		search(range(int(n)), float(x))
	case [_, n]:
		a = range(n := int(n))
		for x in range(-1, n+1):
			search(a, x)
	case [_, *xs, x, f]:
		if f[0] == 'r':
			cmp = gt
		search([*map(int, xs)], float(x))
	case _:
		repl()