Finding the Boundary with Binary Search
Prereq: Binary Search Introduction
An array of boolean values is divided into two sections; the left section consists of all
false and the right section consists of all
true. Find the boundary of the right section, i.e. the index of the first
true element. If there is no
true element, return -1.
arr = [false, false, true, true, true]
true's index is 2.
Try it yourself
The binary decision we have to make when we look at an element is
- if the element is
false, we discard everything to the left and the current element itself.
- if the element is
true, the current element could be the first
truealthough there may be other
trueto the left. We discard everything to the right but what about the current element?
We can either keep the current element in the range or record it somewhere and then discard it. Here we choose the latter. We'll discuss the other approach in the alternative solution section.
We keep a variable
boundary_index that represents the leftmost
true's index currently recorded. If the current element is
true, then we update
boundary_index with its index and discard everything to the right including the current element itself since its index has been recorded by the variable.
1from typing import List 2 3def find_boundary(arr: List[bool]) -> int: 4 left, right = 0, len(arr) - 1 5 boundary_index = -1 6 7 while left <= right: 8 mid = (left + right) // 2 9 if arr[mid]: 10 boundary_index = mid 11 right = mid - 1 12 else: 13 left = mid + 1 14 15 return boundary_index 16 17if __name__ == '__main__': 18 arr = [x == "true" for x in input().split()] 19 res = find_boundary(arr) 20 print(res) 21
The good thing with this approach is that we don't have to modify the while loop logic in the vanilla binary search from the last module, besides introducing a variable.
Another approach to handle case 2 above is to keep the current element in the search range instead of discarding it, i.e.
if arr[mid]: right = mid instead of
right = mid - 1. However, doing this without modifying the
while condition will result in an infinite loop. This is because when
left == right,
right = mid will not modify
right and thus, not shrink search range and we will be stuck in the while loop forever. To make this work we have to remove the equality in the
while condition. In addition, as mentioned in the last module, a
while loop without equality will miss the single-element edge case so we have to add an additional check after the loop to handle this case. Overall, we have to make three modifications to the vanilla binary search to make it work.
Side note: how to not get stuck in an infinite loop
- make progress in each step
- have an exit strategy
This problem is a major 🔑 in solving future binary search-related problems. As we will see in the following modules, many problems boil down to finding the boundary in a boolean array.