CODEWITHSUNDEEP
pythonsearchbinary
Matthew D
Matthew D

Reputation: 154

Python - Altering my binary search function

I wrote the following code:

def binary_search(key,lst):
    """ iterative binary search
        lst better be sorted for binary search to work"""
    n=len(lst)
    lower=0
    upper=n-1
    outcome=None   # default value
    while lower<=upper:
        middle=(upper+lower)//2
        if key==lst[middle].name:    # item found
            outcome=lst[middle]
            break  # gets out of the loop if key was found
        elif key<lst[middle].name:   # item cannot be in top half
            upper=middle-1
        else:        # item cannot be in bottom half
            lower=middle+1           
    return outcome

I am trying to alter it in order to make it divide the list to 3 parts instead of 2. I mean that it wont be binary search anymore but for each iteration the algorithm will divide the list to 3 sections.

I wasn't able to implement this.

Any help will be appreciated.

Upvotes: 0

Views: 230

Answers (1)

Marga Manterola
Marga Manterola

Reputation: 642

You need to divide the list into 3 parts, for that you need two middles: upper_middle and lower_middle. You need to add more clauses to your if. if it's smaller than the lower middle, then it's the first third, if it's higher than the upper it's the last third, otherwise, it's in the middle third.

Keep in mind that even if this is a good exercise for programming, it's not really more efficient because the order of the function stays the same (log n).

Upvotes: 2

Related Questions