Greetings fellow Pythonistas!
I am learning foundations of algorithmic design. I am trying to write a basic binary search function. I have made two separate attempts. They are both broken. I don’t know why. Below are my two specimens along with their corresponding REPL inputs and outputs where I demo the errors and tracebacks. Comments, tips, feedback welcome.
Here is the pseudo code provided by the instructor in the non-credit Udemy course I am taking:
This function accepts a sorted array and a value
Create a left pointer at the start of the array, and a right pointer at the end of the array
While the left pointer comes before the right pointer
Create a pointer in the middle
If you find the value you want, return the index pointer
If the value is too small, move the left pointer down
If the value is too large, move the right pointer up
Else return not present
Here is my first script where I attempt writing the algorithm using recursion:
def binary_seek(ordered_list, value):
left_pointer = ordered_list[0]
right_pointer = ordered_list[-1]
while left_pointer < right_pointer:
center_pointer = int(len(ordered_list)/2)
if center_pointer == value:
return f"Found at: {center_pointer}"
elif center_pointer < (ordered_list[left_pointer] < ordered_list[center_pointer]):
new_list = ordered_list[left_pointer:center_pointer]
return binary_seek(new_list, value)
elif center_pointer < (ordered_list[center_pointer] < ordered_list[right_pointer]):
new_list = ordered_list[center_pointer:right_pointer]
return binary_seek(new_list, value)
return "Not present"
Here is the REPL demo:
$ python
<<< from script1 import binary_seek
<<< binary_seek([ 1, 3, 4, 6, 8, 9, 11, 12, 15, 16, 17, 18, 19 ],18)
Traceback (most recent call last):
File “”, line 1, in
File “/home//file location/script1.py”, line 11, in binary_seek
elif center_pointer < (ordered_list[center_pointer] < ordered_list[right_pointer]):
~~~~~~~~~~~~^^^^^^^^^^^^^^^
IndexError: list index out of range
<<<
Please take note: At that line highlighted in the traceback, I tried adding -1 and +1 after ‘right_pointer’ which did not resolve or change any thing. I am grappling at straws there.
Here is my next attempt:
def binary_seek(ordered_list,elem):
start = 0
end = ordered_list[-1]
middle = (start + end) // 2
while (ordered_list[middle] != elem) and (start <= end):
print(start, middle, end)
if elem < ordered_list[middle]:
end = middle -1
else:
start = middle + 1
middle = (start + end) // 2
if ordered_list[middle] == elem:
return middle
return False
When I run : binary_seek([ 1, 3, 4, 6, 8, 9, 11, 12, 15, 16, 17, 18, 19 ],18) Python begins iterating an infinite loop with the print output of: 0 9 8. The printed output always results in an infinite loop with the same ‘0 9 8’ repeating over and over regardlss which elem variable I pass in.