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.

Answer 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