Your binary search is flawed in various ways, but don't feel bad. It's a
deceptively difficult
algorithm to get right.
The primary problem: confusion between indexes and values. Some of your
code bisects the sequence using index-based logic; other parts rely on
value-based logic (taking the average of highest and lowest values).
In addition to overcomplicating the implementation, that creates some bugs:
Given [1, 3] and 2.
Incorrectly says 2 is in the sequence.
Given [1, 5] and 2.
Gets stuck in an endless loop.
A edge case bug: empty sequences. Given an empty sequence, binary
search should return None; your code blows up with an IndexError.
A performance problem: data copying. Your code makes copies of the input
sequence. That's not needed if we stick entirely to index-based logic for
bisecting.
A software engineering problem: binary search should be written as a
function. Put your code in functions, even in small scripts. There are many
reasons for this, and those reasons are particularly compelling when writing
algorithmic code like binary search. Such a function should take the sequence
and target value as input and return the target's index or None. It should not
print messages to the user: leave that to a different part of the program. When
you put the algorithm inside a side-effect-free function you make it much
easier to test: and a problem like binary search, with its many pitfalls,
requires some real testing.
Start on a good foundation: functions. We need a binary search function and
a main function to exercise the code with some tests. We already have some test
cases: the bugs noted above. As you write the code, try to
think of the various edge cases to be explored and write a test for each one.
def main():
TESTS = [
([], 2, None),
([1, 3], 2, None),
([1, 5], 2, None),
([1, 2, 3], 2, 1),
]
for test in TESTS:
xs, target, expected = test
result = binary_search(xs, target)
if result == expected:
print('ok')
else:
print(f'{test} : {result}')
if __name__ == '__main__':
main()
Binary search: do the bisecting with indexes, not values. Here's
a good starting point. You can fill in the rest of the logic.
def binary_search(xs, target):
i = 0
j = len(xs) - 1
while i <= j:
mid = (i + j) // 2
# Compare xs[mid] to the target, either returning mid
# or modifying i and j.
...
return None