from bsearch import bsearch;
def main():
test_cases = (
((1,2,3), 4),
((1,3,5,6), 0),
((10,20,30,40,50,60,70,80), 25),
((5,10,15,25,30), 16),
((0,2,4,6,8,10,12,14,16), 10),
([], 7),
((0,2,2,2,3,4,5), 1),
((1,2,3), 3),
((1,2,3,4,5,6), 5),
((1,), 1),
((2,), 1),
((1,2), 3),
((1,2), 1),
((1,2), 2)
);
for t in test_cases:
print(f"Is {t[1]:<10} in {str(t[0]):<40}? {bsearch(t[0], t[1])}");
if __name__ == '__main__':
main()
'''
Define a function bsearch that takes two arguments:
- a container
- an element to search for.
Returns whether the element was in the container.
Correct output:
Is 4 in (1, 2, 3) ? False
Is 0 in (1, 3, 5, 6) ? False
Is 25 in (10, 20, 30, 40, 50, 60, 70, 80) ? False
Is 16 in (5, 10, 15, 25, 30) ? False
Is 10 in (0, 2, 4, 6, 8, 10, 12, 14, 16) ? True
Is 7 in [] ? False
Is 1 in (0, 2, 2, 2, 3, 4, 5) ? False
Is 3 in (1, 2, 3) ? True
Is 5 in (1, 2, 3, 4, 5, 6) ? True
Is 1 in (1,) ? True
Is 1 in (2,) ? False
Is 3 in (1, 2) ? False
Is 1 in (1, 2) ? True
Is 2 in (1, 2) ? True
'''
def bsearch(c,e):
v=len(c)-1//2
while (not c[v]==e and not c==[]):
while (e<c[v] and not c[v]==e):
v//=2
if (not c[v]==e):
c=c[:v]
v=len(c)-1//2
if (c[v]==e):
return True
return False