A frequent question I ask when interviewing some candidates is binary search. It cannot be more easier to write a binary search, but the variant may be challenging. For example, upper bound for the given target. When should I shrink my scope to left?

This post elucidates the steps of binary search by illustrating some common mistakes and sloving a problem in LeetCode. And I will remind what should be paid more attention when doing search.

The Problem lists as the following Find Smallest Letter Greater Than Target, which is obvious a case of binary search.

Terminal Condition for Loop

Some candidates wrote the following code confidently.

class Solution:
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        start, end = 0, len(letters) - 1
        double = letters + [letters[0]]
        while start <= end:
            mid = (start + end) // 2
            if double[mid] <= target:
                start = mid + 1
            else:
                end = mid

        return double[start] if double[start] > target else double[start + 1]

A skilled programmer can detect the endless loop by while start <= end. If the condtion goes to else: end = mid, the end is equal to start perpetually.

This is a manifest mistake, but few people may not notice.

Shrink Searching Scope

A more sophisticated engineer bypasses the above trap and wrote down,

class Solution:
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        start, end = 0, len(letters) - 1
        double = letters + [letters[0]]
        while start < end:
            mid = (start + end) // 2
            if double[mid] > target:
                end = mid - 1
            else:
                start = mid

        return double[start] if double[start] > target else double[start + 1]

It is also an endless loop, as many of candidates may not realized. Take Case 3 into consideration:

import unittest

from code import Solution

class TestDict(unittest.TestCase):
    def testResult(self):
        s = Solution()
        # Case 1
        ret = s.nextGreatestLetter(["c", "f", "j"], "a")
        self.assertEqual(ret, "c")

        # Case 2
        ret = s.nextGreatestLetter(["c", "f", "j"], "c")
        self.assertEqual(ret, "f")

        # Case 3
        ret = s.nextGreatestLetter(["c", "f", "f", "j"], "f")
        self.assertEqual(ret, "j")

if __name__ == '__main__':
    unittest.main()

Do you get the point? You want to address the upper bound for target and you move the end index backwards. That’s the root cause. The condition double[mid] > target cannot ensure the element at the index mid - 1 is larger than target.

So when you try to locate the upper bound, move start index on the left rather than end index on the right.

Condition for Shrinking

OK, let’s take a look at the following snippet which move start forward.

class Solution:
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        start, end = 0, len(letters) - 1
        double = letters + [letters[0]]
        while start < end:
            mid = (start + end) // 2
            if double[mid] < target:
                start = mid + 1
            else:
                end = mid

        return double[start] if double[start] > target else double[start + 1]

The title of this section may hint you that the condition for moving index double[mid] < target is wrong. Yes it is. when double[mid] == target in this case, you move the end to mid, which may include the element equal to the given target. The correct operation is moving start to mid + 1.

Accepted Version

Finally, this version seems advisable, and it is accepted.

class Solution:
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        start, end = 0, len(letters) - 1
        double = letters + [letters[0]]
        while start < end:
            mid = (start + end) // 2
            if double[mid] <= target:
                start = mid + 1
            else:
                end = mid

        return double[start] if double[start] > target else double[start + 1]

See this problem Find Minimum in Rotated Sorted Array if you need more practice.