0

I am learning the algorithm now and have a question on the recursive approach to the binary search. I tried to code by myself as following:

def binary_search_rec(x, value):
    x.sort()
    length = len(x)
    if length == 1 and x[0] == value:
        return 0
    elif length == 1 and x[0] != value:
        return 'none'
    else:
        low = 0 
        high = length - 1
        mid = (low + high)//2
        if value == x[mid]:
            return mid
        elif value > x[mid]:
            return mid + binary_search_rec(x[mid+1:], value)
        else:
            return binary_search_rec(x[0:mid], value)

The base case is an array with single element. However, I can't receive the correct result with the toy data:

binary_search_rec([1, 2, 3, 4], 3)

which will return 1.

Would you please help me figure out where I did wrong? Thank you in advance for your help.

Improve this question
4
  • return mid + 1 + binary_search_rec(x[mid+1:], value) Commented Aug 31, 2020 at 2:33
  • Also need to expect sorted input — you shouldn't be sorting it at all in the input if you are returning an index. If you are returning indices the called would expect these to be the index of the input, not the index of the list after you sort it. Commented Aug 31, 2020 at 2:46
  • @Julien Thank you for your help. I should double check why I need to add additional 1 here. Commented Aug 31, 2020 at 14:06
  • @MarkMeyer Thank you for your help. I should update the input with the sorted list rather than an unsorted list. Commented Aug 31, 2020 at 14:07

2 Answers 2

Reset to default
1

This Code May help you up, based on your code, I have few modifications.

def binary_search_rec(x, value):
x.sort()
length = len(x)
if length==0 or length ==None:
    return -float('inf')
elif length == 1 and x[0] == value:
    return 0
elif length == 1 and x[0] != value:
    return -float('inf')
else:
    low = 0 
    high = length - 1
    mid = (low + (high-low))//2
    if value == x[mid]:
        return mid
    elif value > x[mid]:
        return mid + 1 + binary_search_rec(x[mid+1:], value)
    else:
        return binary_search_rec(x[0:mid+1], value)

print(binary_search_rec([1, 2, 3, 4, 5], 3))

Output: 2 (index)

'none' string return is not a good idea though, instead of returning 'none' you may return inf value.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

If you get helped from my solution then upvote the answer.
Thank you for your help, @Shaonsani. I think the key update here is: 1. replace the 'none' with -float('inf'); 2. add 1 in when value > x[mid]. I am wondering the meaning of the -float('inf')? Thx.
Yeah. if you add a string to an integer then it seems wrong. so I use -float('int') in that case.
Get it. Thank you, Shaonsani.
1

If you want to return the index of the found number using a recursive approach, you need to keep track of the indices relative to initial list. Passing slices back into the recursion will return the index relative to that slice, which is not the correct answer. An easier approach is to pass the low and high values into the recursion along with the the original list rather than the slice. You can handle this with default values so you don't burden the caller with calculating this. This will be both easier to reason about and faster because you are not allocating new copies of the list slices with every recursive call. For example:

def binary_search_rec(x, value, low = 0, high = None):
    if high is None:
        high = len(x) 

    # edge case -- we didn't find it
    if high <= low :
        return 'none'

    # the mid is relative to the whole list, so add low to it
    mid = (high - low) // 2 + low   

    if value == x[mid]:
        return mid 
    elif value > x[mid]:
        return binary_search_rec(x, value, mid + 1, high)
    else:
        return binary_search_rec(x, value, low, mid)


for i in range(8):
    print(binary_search_rec([1, 2, 3, 4, 5, 6], i))

Prints:

none
0
1
2
3
4
5
none

Also, sorting the input doesn't make sense if you are returning the index — you should expect the caller to pass sorted input. If the caller passes binary_search_rec([3, 2, 1], 1) and you return 0 because that's the index of the sorted list, it's not really helpful to the caller.

Improve this answer

9 Comments

Thank you for your explanation, Mark. I am wondering why we need to add high = None in the function statement? And should we use mid - 1 rather than mid for the case of value < x[mid]?
Setting the default of high to None allows you to know when you need to supply the value. You need to do this because you can’t put high = len(x) in the function signature. Whether you use mid - 1 or mid + 1 later is a matter of preference so long as the result is correct. I would also recommend returning None or -1 instead of ”none” when the value is not found.
I see. Thank you for your help, Mark. What is the difference between placing high=len(x) and high=None? Does it mean that I can update the high value later with setting high=None, however, I can't make this in the setting high=None.
I also have an additional question. In the recursion, we have base case and recursive case. I would like to check what is the base case in your program? Besides, I think the main reasons that we +1 or -1 is to reach the edge case, which will stop the program and return the values. Without them, how should we return the final values? Thanks.
The base case is when high == low. This happens with an empty list because low and high are both 0. It also happens after you have looked though the whole list. You will always reach this edge case because you are calling the recursion on smaller groups each time by passing in the mid (or mid + 1) as either high or low. Eventually low will equal high.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.