Binary search implementation conditional confusion

I was solving problems using binary search and I became confused when I saw that in some places people have used while start < end but in the algorithm my understanding is that it should be while start <= end.

For example, here is a solution to the Leetcode problem Find Smallest Letter Greater Than Target:

def nextGreatestLetter (self, letters: List[str], target: str) -> str:
    l, r = 0, len(letters)-1

    # cross the border
    if target >= letters[-1]:
        return letters[0]

    while l < r:
        mid = (l+r)//2
        if letters[mid] <= target:
            l = mid+1
        else:
            r = mid
    return letters[l]

why haven't we decremented r = mid - 1 and why is not there while l <= r? I am really confused.

Solution

Those are implementation details. There are multiple ways of implementing everything.

In this case, the loop condition is l < r (not l <= r ) because when l == r (i.e., there’s only one element in the search space) then we don’t have to process further and the expected result(ceil) is the element at position l.

And the updation statement is r = mid (not r = mid - 1) because that updation is happening when target < letters[mid] and we cannot discard the element at mid, based on this condition. Suppose for example the element at (mid - 1) could be smaller or equal to the target, in that case our result would be the element at mid.

Like I said these are just the implementation details and the same solution could be implemented like this as well:

def nextGreatestLetter (self, letters: List[str], target: str) -> str:
    l, r = 0, len(letters)-1

    # cross the border
    if target >= letters[-1]:
        return letters[0]

    while l <= r:
        mid = (l+r)//2
        if letters[mid] <= target:
            l = mid+1
        else:
            r = mid - 1
    return letters[l]

This implementation where we're processing the l == r case inside the loop is also correct and passes all the test cases on Leetcode.

PS: I'm assuming you've recently started competitive coding, so just a suggestion for you. Do not try to remember the implementation and concentrate on the crux of the algorithm, again because there are multiple ways of implementing the same algorithm.