Click here to Skip to main content
15,745,574 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
def bsearch2 ( lst : list , key , lo :int , hi : int ):
    if lo == hi :
       return None # key not in empty segment
    m = ( lo + hi )//2 # position of root
    if lst [ m] == key :
        return m
    elif lst [ m] > key :
        return bsearch2 ( lst , key , lo , m)
    else : # lst[m] < key
        return bsearch2 ( lst , key , m +1 , hi )

What I have tried:

Updated 16-Sep-20 9:52am

Why do you think? What would change if you didn't?

Do two things:
1) Read this: Binary search algorithm - Wikipedia[^]
2) Break out the debugger and follow your code through as is. Now change "m + 1" to "m" and try it again. What changed? Why didn't it work?

Try it - invest some time in looking at what happens, and think about it. That will give you a much better grasp of how algorithms work in general that just being told "because ..."
Share this answer
Ahmad Qassym 16-Sep-20 15:10pm    
the problem i have programming exam after few days and there is no time to learn new things or techniques :D
The same answer as you were given four days ago at[^]. Did you follow the suggestions?
Share this answer
Same question as Why do we add 1 to the r + m in the last line ?[^] with mostly same code.
m+1 is not alone it foes with other variables:
elif lst [ m] > key :
    return bsearch2 ( lst , key , lo , m )
else : # lst[m] < key
    return bsearch2 ( lst , key , m +1 , hi )

Think about the meaning if those variables in each call to bsearch2.
Take a sheet of paper and a pencil, write a sorted list and simulate the meaning of each variables in the list as search is going on.
Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900