Find the First True in a Sorted Boolean Array

Prerequsites : 🍦Binary Search(Vanilla)

Question

An array bools is given, divided into two halves, the left half consists of all False values and the right with all True. Find the index of the first True Element. If there is no True value in the array return -1.

bools = [F,F,F,T,T,T]

result = 3

Intuition

1. Can we reduce the search space in an array with sorted false and true values?
2. During a binary search, we narrow down the search space by dividing it in half with each iteration. This is accomplished by removing either the entire right or left side of the search space, based on the location of the midpoint and its relationship with what we are looking for. How can that be applied to a sorted boolean array?
3. False values are positioned at the start (left side) of the array, followed by true values. As soon as we encounter a false value, we can safely discard all values to its left and focus only on the remaining true values to its right.

4. At True Value, we have identified a potential value that can be stored, but we are unsure if it is the first True value. If the element we are on is not the first and all values to its right are True, then the first True value must be on the left side of it. Therefore, we can discard all values to the right. By iterating from right to left, we constantly update and obtain the most current and leftmost potential True value.

Implementation

Using the base template used in 🍦Binary Search(Vanilla)

1. Left: lowest possible index, right: highest possible index
2. Using a while loop, based on the value we are on. If true, store the possible value and chop the range from the right side. If false, chop the range from the left side. Will return the possible value if found, else will return the default -1 as the possible value.

Keeping with the Vanilla Tradition Code

class Solution:

    def firstTrue(self, bools):

        (left, right) = (0, len(bools) - 1)
        possibleValue = -1

        while left <= right:

            mid = left + (right - left) // 2
						
					# True
            if bools[mid]: 
                possibleValue = mid
                right = mid - 1
						
					# False
            else:
                left = mid + 1

        return possibleValue

SandBox PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition

For Further Understanding

Find the First True in a Sorted Boolean Array (Optional Alternate Approach) Really interesting way to solve the same problem

⛔First Bad Version (Practice)—Practice the leetcode Version

Follow-up

How will you go about solving for the last true value, like the array below?

bools = [T,T,T,F,F,F]