Why we write m+1 in the last line of the binary search code ?

Question

1.00/5 (1 vote)

See more:

Python

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:

.................................................................

Posted 16-Sep-20 8:35am

Ahmad Qassym

Updated 16-Sep-20 9:52am

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

OriginalGriff · Accepted Answer · 2020-09-16T08:58:00

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

Do two things:
1) Read this: Binary search algorithm - Wikipedia[^]
And
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 ..."

Richard MacCutchan · Accepted Answer · 2020-09-16T09:21:00

Solution 2

The same answer as you were given four days ago at https://www.codeproject.com/Questions/5279256/Why-do-we-add-1-to-the-r-plus-m-in-the-last-line[^]. Did you follow the suggestions?

Posted 16-Sep-20 9:21am

Richard MacCutchan

Patrice T · Accepted Answer · 2020-09-16T09:52:00

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:

Python

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.

Why we write m+1 in the last line of the binary search code ?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0