How to properly recursively call alternative type of binary search (python)?

Question

I get the gist of binary search, but I'm having trouble understanding why this incomplete (because I haven't specified side that I want the search to run on) code won't even return any value (such as for lists of small length).

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bin_search(start, end, nums, target):
            mid = int((start+end)/2)
            if start >= end:
                return -1     
            if nums[mid] == target:
                return mid
            elif nums[start] == target:
                return start
            elif nums[end] == target:
                return end
            bin_search(mid, end-1, nums, target)
            bin_search(start+1, mid, nums, target)


        output = bin_search(0, len(nums)-1, nums, target)
        return output

Taken from the following leetcode: https://leetcode.com/problems/search-in-rotated-sorted-array/

I am aware of what this SHOULD look like - in those cases, people check only if the MID of the sub_list equals our target. I don't see why I shouldn't check the start and end either.

Additionally, the code above, even when it finds the index of the target, it won't properly return when recursion has ended.

Any advice is greatly appreciated. I do want to repeat, I realize I haven't specified which side the binary search should run on, but, I'm just trying to understand why it won't even return any value.

Thanks.

score 2 · Answer 1 · answered Nov 07 '19 at 22:38

2

You return a value only for the base cases. In the "normal" cases

        bin_search(mid, end-1, nums, target)
        bin_search(start+1, mid, nums, target)

you return nothing. Thus, when you work your way back up the stack to the original call, there is no return value. Try

        r_search = bin_search(mid, end-1, nums, target)
        l_search = bin_search(start+1, mid, nums, target)
        return max(r_search, l_search)

answered Nov 07 '19 at 22:38

Prune

76,765
14
60
81

1

You'd really compute a value for `l_search` even though there's a good possibility you'll never need it? I wouldn't call the second bin_search() until I had determined the first one didn't succeed. – cdlane Nov 07 '19 at 23:04
You're quite correct. I'm not trying to fix the entire routine, only the immediate problem. OP has more to work on ... – Prune Nov 07 '19 at 23:19

Mohd · Accepted Answer · 2019-11-07T23:06:27.307

1

It wouldn't return any value because you are not returning anything unless you find the element, so if on the first call it doesn't find the element, nothing will be returned. To keep looking for a value recursively you should add return before recursively calling the function like:

def bin_search(start, end, nums, target):
    mid = int((start+end)/2)
    if start >= end:
        return -1     
    if nums[mid] == target:
        return mid
    elif nums[start] == target:
        return start
    elif nums[end] == target:
        return end
    s1 = bin_search(mid, end-1, nums, target)
    if s1 >= 0:
        return s1
    return bin_search(start+1, mid, nums, target)

However you should work on your implementation of binary search. For example, you should choose where to go when you don't find the element and reduce the two calls to one call. I would also suggest trying an iterative approach of binary search like:

def bin_search(start, end, nums, target):
    # suppose we're just looking for the number in a sorted array
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            end = mid-1
        else:
            start = mid+1
    return -1

edited Nov 07 '19 at 23:06

answered Nov 07 '19 at 22:40

Mohd

5,523
7
19
30

You'd really compute a value for `s2` even though there's a good possibility you'll never need it? `return s1 if s1 >= 0 else s2`. I wouldn't call the second `bin_search()` until I had determined the first one didn't succeed. – cdlane Nov 07 '19 at 22:52
@cdlane that's exactly what I wrote below the code :) – Mohd Nov 07 '19 at 22:53
I didn't get that from the *"reduce the two calls to one call"* comment. It's still two calls. – cdlane Nov 07 '19 at 22:54
The first code was a fix to OP's approach, what I said afterwards is that you don't really need the two calls, when binary searching you will always discard half of the range and do one call instead, which is implemented in the iterative example @ the end – Mohd Nov 07 '19 at 22:56
Checking whether the first call succeeded or not would be more efficient but the whole approach should be changed to be more efficient which is why I mentioned the 2nd approach, edited anyways thanks =) – Mohd Nov 07 '19 at 23:01

How to properly recursively call alternative type of binary search (python)?

2 Answers2