Skip to content

Instantly share code, notes, and snippets.

@brianherman
Last active November 26, 2020 03:18
Show Gist options
  • Save brianherman/7e58b48ddbb7060663139416ed4901fa to your computer and use it in GitHub Desktop.
Save brianherman/7e58b48ddbb7060663139416ed4901fa to your computer and use it in GitHub Desktop.
import math
import random
def search(array, key):
if len(array) == 0: return -1
hits = 0
max_value = 4294967296
min_value = 0
lower = 0
upper = len(array) - 1
index = math.floor((key - min_value) / (max_value - min_value) * (upper - (lower + 1))) + lower
while True:
hits += 1
value = array[int(index)]
if value > key:
upper = index - 1
max_value = value
elif value < key:
lower = index + 1
min_value = value
elif value == key:
return hits, index
if upper < lower:
return hits, -1 * lower - 1
index = math.floor((key - min_value) / (max_value - min_value) * (upper - (lower + 1))) + lower
def generate(N):
return sorted([random.random() for i in range(N)])
def expected_hits(N):
t = generate(N)
expected = 0
tests = 1000
for _ in range(1, tests):
index = int(random.uniform(0, N - 1))
key = t[index]
hits, found_index = search(t, key)
assert t[found_index] == key
expected += hits
return expected / tests
if __name__ == "__main__":
for N in range(1, 1000000000, 10):
hits = expected_hits(N)
print (f"N {hits}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment