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.