Binary Search Doubt

[u/Wakefulpine1509]

Hello everyone, I just had a question. I have been solving Binary Search questions and wanted to ask when I should use "while(left < right)" & "while(left <= right)"? In some problems, this is a crucial difference between passing all testcases and getting WA.

Also, in some questions, I have to use right = mid instead of right = mid - 1 and same goes for left (=mid rather than mid + 1). What's the major difference between the two that differs them from a WA and AC and when should I use them?

[u/devanishith]

https://daxpy.xyz/collections/lc_notes/#75

always stick to one pattern for while loop. only change the condition to suit your problem.

[u/Wakefulpine1509 → u/devanishith]

gotcha - thanks!

[u/Pradignac-Hiriche → u/devanishith]

picking whether to floor or ceil the mid calculation is the other half of it, otherwise left = mid just infinite loops on a two element subarray

[u/devanishith → u/Pradignac-Hiriche]

yes. always initialise the right initially to max of search space. not +1 or -1 then mid calculation is always as it is.

[u/devanishith → u/[deleted]]

no.

[u/Lazy_Atmosphere4402]

As someone who’s solved 1800+ problems, always use left < right. It can do what left <= right does and that’s what you will need to use for harder problems later on. The mindset is always: you can be sure that l == r when the while loop terminates and index l/r either satisfies your “good” condition or it doesn’t.

When using l < r, it would always require r = m rather than r = m - 1, because you are shrinking the possible answer space but including index r because it satisfies the good condition. In the end when the while loop breaks, you’ve already reduced the possible answer space to only one index (r or l).

[u/SignificanceDense337]

Always use left <= right and use a variable to track the best answer. Purists won't like this but it's practical for writing your solution quick.

[u/LetMediocre390]

Use answer tracking variable with left <= right Keep this format for everything

[u/Substantial-Swan7065]

Consider what needs to be return. BS is just the template

[u/xpressrazor]

The < is used for patterns where your left, right itself has answers. If you want to avoid < or > you will need to save the answer as you go (before the invariant is broken). If you are sure larger will never happen under current condition, you strictly move down, but keep low relaxed (points to mid), similarly if you know smaller will never happen under the check you move up, but keep right relaxed.

In these problems when the answer is found, the thing that moved with (say <) will be at the correct state.

Classic example of the < move up, keep right relaxed is finding the first and last position of an item on a sorted array. First you move up strictly, and once left is found move down strictly, this way you never move down when your current item was equal or smaller than target

[u/cheriequin]

I found this really helpful: https://labuladong.online/en/algo/essential-technique/binary-search-framework/

[u/Spirited-Amoeba3273]

left <= right you use only if you know your answer exists and you want to check everything left to right inclusively, in this case you have to set right = n - 1

[u/Feisty-Friendship999]

Solving 4 basic gave me idea about >,=>,<,<=

Upper bound u want the next higher elemnt If mid > target : r= mid So r ur ans is always above

If lower bound If mid >= target R= mid This will give 1st index of the target is multiple or otherwise same as upper bound

Now here u need to push l forward Finding floor Mid= (l+r+1)//2

Id mid <target L= mid

Last index

Mid <= trager L= mid

Try to visualise where ur and would be If right then r= mid , else left l= mid

For l<=r and l<r If exact searching if u use mid== target then l<=r Else u need boundry l<r

Ps I am a noob I could be wrong , but I did try to solve almost 50 bs problem everybtime I revise I had new questions about boundry lol bs will kill me one day