CODEWITHSUNDEEP
pythonalgorithmrecursionbinary-search
Owen Brain
Owen Brain

Reputation: 35

recursive binary search of a sorted sublist

I am trying to implement a recursive binary search algorithm which takes 4 arguments, a list, first, the integer index of the first item in the sorted sub-sequence, last, the integer index of the last item in the sorted sub-sequence and a target which will be compared to the values stored in the list.

The algorithm needs to return the position of the target within the sorted sub-sequence (if it exists) and if not return the position in which it should be placed within the sorted sub-sequence.

Here's what I have thus far;

def binary_search(a_list, first, last, target):
    subMidpoint = (first + last) // 2
    if a_list[subMidpoint] == target:
        return subMidpoint
    else:
        if target < a_list[subMidpoint]:
            last = subMidpoint -1
            return binarySearch(a_list, first, last, target)
        else:
            first = subMidpoint +1
            return binarySearch(a_list, first, last, target)
    return first

I am struggling to wrap my head around how it will return the position if the item does not exist, any help would be greatly appreciated. The code currently compiles however is returning 'None' rather than an index position.

Many Thanks in advance.

Edit;

Thanks all for your help, I have managed to alter the final clause and it has passed some tests however it fails when the target is less than the smallest value in first and when the target is greater than the value in last.

Here's the altered final clause.

    else:
    if target < a_list[subMidpoint]:
        last = subMidpoint -1
        return binary_search(a_list, first, last, target)
    else:
        first = subMidpoint +1
        return first

Upvotes: 0

Views: 530

Answers (2)

Owen Brain
Owen Brain

Reputation: 35

Solved, thanks everyone. Not the cleanest solution but it works.

def binary_search(a_list, first, last, target):
subMidpoint = (first + last) // 2
if target < a_list[first]:
    return first
elif target > a_list[last]:
    return last +1
elif a_list[subMidpoint] == target:
    return subMidpoint
elif target < a_list[subMidpoint]:
    last = subMidpoint -1
    return binary_search(a_list, first, last, target)
else:
    first = subMidpoint +1
    return first

Upvotes: 0

Prune
Prune

Reputation: 77847

You almost have your answer in your description: if you get down to adjacent items, say positions 5 and 6, and you haven't found the item, then it would be inserted between those two. Since list indices grow to the upper end, you'd return the higher of the two -- 6, in this case.

Thus, your logic would be in your last clause

else:
    if subMidpoint == first:
        return last
    else:
        first = subMidpoint +1
        return binarySearch(a_list, first, last, target)
  • Drop that return first at the bottom; you should not be able to reach that statement.
  • Learn the elif keyword; your program will be more readable.

Upvotes: 0

Related Questions