Basic binary search algorithm - using a while loop

[Drone4four]

I’m learning algorithms using Python. My latest challenge laid out by the instructor in my highly sophisticated non-accredited Udemy course content I am watching is to write a basic binary search algorithm.

Here is the pseudo code:

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

This is the implementation I came up with:

def binary_seek(array,target):
   start = 0
   end = array[-1]
   middle = (start + end) // 2
   print(f'Initialization: {start}, {middle}, {end}')
   while (array[middle] != target) and (start <= end):
       print(start, middle, end)
       if target < array[middle]:
           print(start, middle, end)
           end = middle -1
           middle = (start + end) // 2
           print(start, middle, end)
       else:
           print(start, middle, end)
           start = middle + 1
           middle = (start + end) // 2           
           print(start, middle, end)
   if array[middle] == target:
       print(start, middle, end)
       return print(f'Found:{middle}')
   else:
       print(start, middle, end)
       return print(f'Not Found')

When I run: print(binary_seek([ 1, 3, 4, 6, 8, 9, 11, 12, 15, 16, 17, 18, 19 ],6)) - - that returns: “Found: 3”. So this works.

But when I proceed to search for the value of 18 (with an index position to the right of the middle of the original array), Python throws an “index out of range” error and I am not sure why. For example, this is the output when trying to search for 18:

Initialization: 0, 9, 19
0 9 19
0 9 19
10 14 19
Traceback (most recent call last):
File “/<location>/algos/basic_binary_search/bbs5.py”, line 26, in
print(binary_seek([ 1, 3, 4, 6, 8, 9, 11, 12, 15, 16, 17, 18, 19 ],18))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File “/<location>/algos/basic_binary_search/bbs5.py”, line 6, in binary_seek
while (array[middle] != element) and (start <= end):
~~~~~^^^^^^^^
IndexError: list index out of range

It breaks before the second iteration of the while loop can execute.

The while loop on its first iteration traverses to the if conditional and since the target is not less than the middle of the array, Python proceeds down to the else operation and on its first pass there successfully repositions the start value to the old middle (10), re-calculates and assigns the new middle (to 14), and the end value remains (19). Since the middle value (10) is not the target, the while loop should run again. But Python chokes there with that “list index out of range” error.

What might you people suggest I try next? Comments? Feedback and tips welcome.

[deanhystad]

Why this?

start = 0
end = array[-1]

If start is an index, why is end an array value?

that returns: “Found: 3. So this works

Returning the correct result for 1 test only means it returns a correct result for one test. It doesn't mean it works. The correct result could be returned for a reason having nothing to do with the correct implementation of the algorithm or the correctness of the algorithm. Testing your code with [1, 3, 4, 6, 8, 9, 11, 12, 15, 16, 17, 18, 19] raises an IndexError for any target > 16. I wouldn't describe that as "works".

Testing tries to find ways that the algorithm fails. If any test finds a fail, it means the algorithm has an error. If all tests pass it only means you didn't write a test that makes the algorithm fail. Unless you can test all possible cases, testing cannot prove that an algorithm works

Your function is useless. It returns None if it finds the target and None if it doesn't. It should return the index of the value or None if the value is not found. Your function should not print any output.

Convention is to have tabs be 4 spaces, not 3.