Python - Altering my binary search function

Question

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.

Why do you want to divide into three parts? The virtue of a binary search is that you don't need to do too many comparisons (just one per iteration). With three parts, you need to do two comparions in many cases (you might be able to short-circuit if the first comparison gives an appropriate result), which outweighs the benefit of reducing the search space from 1/2 to 1/3 per iteration. — Blckknght
– Blckknght, Commented Apr 9, 2013 at 19:11
it is an assignment. I am aware it's not more efficient in any way. — Matthew D
– Matthew D, Commented Apr 9, 2013 at 19:20

Marga Manterola · Accepted Answer · 2013-04-09 19:11:04Z

2

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).

answered Apr 9, 2013 at 19:11

Marga Manterola

6421 gold badge4 silver badges12 bronze badges

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

2 Comments

Matthew D Over a year ago

I tried and i still couldn't really get it the way you decsribed. Do you mean I should have 3 parts to the list? the middle, upper middle, and lower middle? I wish to alternate my own code to work for this search and not write a whole new one so could you guide me a bit more? I'm having trouble setting the limits to default values and knowing how to check if the key is in there.

Marga Manterola Over a year ago

Yes, you need three parts to the list. And you need to rewrite the whole function. There's no point in avoiding that, you need to do it, or it's not going to be tertiary search.

Collectives™ on Stack Overflow

Python - Altering my binary search function

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related