Binary Search

search.py

import random
import logging
from sys import argv

comparisons_done = 0

logging.getLogger().setLevel(logging.DEBUG)

def binary_search(list, target):
	logging.debug(f'list: {list}')
	if list is None or len(list) == 0:
		logging.debug('list is none/empty')
		return None

	midpoint = len(list) // 2
	logging.debug(f'midpoint: {midpoint}')

	logging.debug(f'comparing target value of {target} to {list[midpoint]}')
	global comparisons_done
	comparisons_done += 1
	if list[midpoint] == target:
		return target

	if midpoint > 0:
		if list[midpoint] < target:
			logging.debug(f'list[{midpoint}] value is < target. Using RHS.')
			return binary_search(list[midpoint+1:], target)
		else:
			logging.debug(f'list[{midpoint}] value ({list[midpoint]}) is greater than {target}. Using LHS.')
			return binary_search(list[0:midpoint], target)

	return None

# my_list = [0, 6, 8, 10, 14, 18, 34, 44, 100, 125, 200, 302, 467, 512, 602, 643, 700, 703, 719, 790, 800, 804]
my_list = sorted([random.randint(0, 10000) for x in range(1000)])
target_value = 643

if len(argv) > 1:
	target_value = int(argv[1])

result = binary_search(my_list, target_value)

logging.info(f'Value found? {result is not None}')
logging.info(f'{comparisons_done} comparisons for list length {len(my_list)}')