Recursive binary search python

Question

I've been trying to write binary search recursively. When I do this using the list[:] syntax I don't get the intended results with several errors coming up or not getting the correct values.

def binary_search(arr, val):

  left = 0 
  right = len(arr)-1
  mid = (left + right)//2

  #Go through the array
   if (val == arr[mid]):
     return mid
   #Check right side of arr
   if (val > arr[mid]):
     return binary_search(arr[mid+1:], val)
   #Check left side of arr
   return binary_search(arr[:mid], val)

EDIT: Example inputs and outputs

arr1 =[]
for i in range(10):
    arr1.append(i)

for i in range(10):
    print(binary_search(arr1,i))

I expect to get something like '0,1,2,3,4,5,6,7,8,9' but get '0,1,0,0,4,None ,None,2,0,0'

Can you give example inputs and show what your function outputs compared to what you expected? — glibdud
– glibdud, Commented Jul 9, 2018 at 15:23
I don't think it makes sense to have a while loop that contains an unconditional return. You'll never loop more than once, that way. (posting this as a comment and not an answer because I don't have any specific recommendations about what you should be doing instead) — Kevin
– Kevin, Commented Jul 9, 2018 at 15:24
@Kevin your'e right. THe while loop is unnecessary so I took that out, but I still get the same errors — handavidbang
– handavidbang, Commented Jul 9, 2018 at 15:34

nosklo · Accepted Answer · 2018-07-09 15:42:27Z

You have two problems. First one is a typo, where you say

if (val > mid):

you should say

if (val > arr[mid]):

Since you're comparing the value and not the index.

Second one is more subtle... when you check the right side of the array, in:

return binary_search(arr[mid+1:], val)

The subarray you're passing to the recursive call (arr[mid+1:]) already starts in the middle of the array, that means the result of that recursive call will return the index of the element in the subarray. So you need to add the index delta you used to split the array, to have a index based on the full array again:

return binary_search(arr[mid+1:], val) + (mid + 1)

Here's the full code for completeness:

def binary_search(arr, val):
  left = 0 
  right = len(arr)-1
  mid = (left + right)//2

  #Go through the array
  if (val == arr[mid]):
     return mid
   #Check right side of arr
  if (val > arr[mid]):
     return binary_search(arr[mid+1:], val) + (mid + 1)
   #Check left side of arr
  return binary_search(arr[:mid], val)

Aidenhjj · Accepted Answer · 2018-07-09 15:47:33Z

0

You're comparing val to mid, instead of to arr[mid]. Also, it would read nicer if you made the ifs mutually exclusive. Also, as per nosklo's answer below, you need to add the index offset for the greater than case:

#Go through the array
if (val == arr[mid]):
    return mid
#Check right side of arr
elif (val > mid):
    return binary_search(arr[mid+1:], val) + (mid + 1)
#Check left side of arr
else:
    return binary_search(arr[:mid], val)

edited Jul 9, 2018 at 15:47

answered Jul 9, 2018 at 15:41

Aidenhjj

1,2891 gold badge14 silver badges29 bronze badges

3 Comments

nosklo Over a year ago

That's not enough to fix it, see my answer

Aidenhjj Over a year ago

@nosklo - thanks, I still prefer my version with the elif / else.

nosklo Over a year ago

Sure! I also prefer if/elif - I like to copy the exact OP's code to help them understand where their process of thought went wrong.

Chamara Herath · Accepted Answer · 2022-10-13 20:50:45Z

Here, more generic binary search recursive function, that returns None if the key not found.

def binary_search(arr, val):
    mid = len(arr) // 2
    if (val == arr[mid]):
        return mid
    if mid == 0:
        return None
    if (val > arr[mid]):
        call_back = binary_search(arr[mid+1:], val)
        return call_back + mid + 1 if call_back is not None else None
    return binary_search(arr[:mid], val)

Result:

arr = list(range(10))
for i in range(15):
    print(binary_search(arr, i))

0
1
2
3
4
5
6
7
8
9
None
None
None
None
None

Collectives™ on Stack Overflow

Recursive binary search python

3 Answers 3

1 Comment

3 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

Comments

Related