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.

• Blckknght: 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.
• Matthew D: it is an assignment. I am aware it's not more efficient in any way.

Answer 1

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

• Matthew D: 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: 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.