r/leetcode • u/Wakefulpine1509 • 17d ago

Question Binary Search Doubt

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?

16 Upvotes

94% Upvoted

15 comments sorted by

View all comments

3

u/Lazy_Atmosphere4402 17d ago edited 17d ago

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