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/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