import random
import statistics
import time
from typing import List, Optional
import matplotlib
import matplotlib.pyplot as plt


# [1, 2, 3, 4, 5], 0
#        ^
#          [4, 5], 3
#              ^
#          [4]   , 3
#           ^

# 3

def blind_binary_search(haystack: List[int], needle: int, offset=0) -> Optional[int]:
	if len(haystack) == 0:
		return None

	partition = len(haystack) // 2

	if haystack[partition] == needle:
		return offset + partition

	if haystack[partition] > needle:
		return blind_binary_search(haystack[:partition], needle, offset)

	return blind_binary_search(haystack[partition + 1:], needle, partition + 1 + offset)


def main():
	print("Correctness testing...")
	try:
		for length in range(10):
			haystack = [i for i in range(length)]

			assert blind_binary_search(haystack=haystack, needle=length) is None
			assert blind_binary_search(haystack=haystack, needle=-1) is None

			for target in range(length):
				assert blind_binary_search(haystack=haystack, needle=target) == target

		for target in range(10):
			assert blind_binary_search(haystack=[], needle=target) is None

		for _ in range(10_000):
			haystack = [random.randint(-100, 100) for __ in range(random.randint(1, 100))]
			haystack.sort()
			needle = random.randint(-100, 100)
			result = blind_binary_search(haystack=haystack, needle=needle)
			if result is not None:
				assert haystack[result] == needle
			else:
				assert needle not in haystack
	except AssertionError as e:
		print("Faaaaaail")
		raise e
	else:
		print("Paaaaasssssss")

	print("Performance testing...")

	average_times = []
	length = 1
	while length < 10_000_000:
		run_times = []
		for _ in range(10):
			haystack = [i for i in range(length)]
			needle = random.randint(0, length)
			start_time = time.time()
			blind_binary_search(haystack=haystack, needle=needle)
			end_time = time.time()
			run_times.append(end_time - start_time)
		average_times.append(statistics.mean(run_times))
		length += 500_000

	plt.scatter(range(len(average_times)), average_times)
	plt.show()


if __name__ == "__main__":
	main()