def binarySearch2(arr, val):
left = 0
right = len(arr) - 1
mid = (left + right) // 2
arr.sort()
if val == arr[mid]:
return True
if val > arr[mid]:
return binarySearch2(arr[mid + 1:], val)
if val < arr[mid]:
return binarySearch2(arr[:mid - 1], val)
for i in range(10):
print(binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9], i))
It keeps telling me index out of range and i'm not sure where went wrong.
In the comments, I pointed out that: binarySearch2 ends up getting called with an empty arr, so the length of that is 0. Since you compute right = len(arr) - 1, that makes right equal to -1. And mid = (left + right) // 2 will also be -1. This is something you don't want to begin with, but trying to index an empty list with -1 is what causes the error. Your recursive function is missing an important stop condition.
You asked why it would be an empty arr.
Your main loop calls binarySearch2 like this on the first iteration:
binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9], 0)
In the function, this means that this condition is True:
if val < arr[mid]: # val == 0, mid == 4, 0 < arr[4]
return binarySearch2(arr[:mid - 1], val) # called with (arr[:4 - 1], 0)
Note that there's a mistake here - you pass arr[:mid - 1] but since the slice is already excluding the element at that index, you're slicing off one element too many. That's not the main problem though.
On this second call, the same thing happens again:
if val < arr[mid]: # val == 0, mid == 1, 0 < arr[1]
return binarySearch2(arr[:mid - 1], val) # called with (arr[:1 - 1], 0)
Already, this causes binarySearch2 to be called as binarySearch2([], 0), causing the error as explained.
Even if you fix the mistake though, and change the code to this:
if val < arr[mid]:
return binarySearch2(arr[:mid], val)
It would still fail because the function is called with val being 0 and since that's a value that's not in the array, this condition still triggers and ends up calling binarySearch2([], 0) on the third iteration.
Your code doesn't account for the case where val simply isn't in the list arr.
A better implementation that does do this:
def binarySearch2(arr, val):
def search(arr, val):
if len(arr) == 0:
return False
left = 0
right = len(arr) - 1
mid = (left + right) // 2
arr.sort()
if val == arr[mid]:
return True
if val > arr[mid]:
return binarySearch2(arr[mid + 1:], val)
if val < arr[mid]:
return binarySearch2(arr[:mid], val)
arr.sort()
return(search(arr, val))
This avoids sorting the list more than once, and it checks if there are values (left) in arr before moving on (the missing stop condition).
There's further optimisation possible. For one, you don't have to keep slicing the list - instead you could just pass along a left and right index and keep narrowing the gap between those. Of course, if you do that, you no longer need a recursive solution either, and you could do this in a simple loop.