Constant Time
Constant Time
/Binary Search
Binary Search
/
Find the First True in a Sorted Boolean Array (Optional Alternate Approach)

Find the First True in a Sorted Boolean Array (Optional Alternate Approach)

Prerequsites : 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array

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

image

Breaking Tradition and changes.

Compared to 🔑Find the First True in a Sorted Boolean Array . We will change a few things here

  1. When we are on a True value Instead of moving right = mid +1 we right = mid as it is a possible value and we will keep it in the range.
  2. Instead of left ≤ right. We will use left < right. When left == right which will make mid the same as left and right and the mid value is True we will never be able to overlap pointers as due to setting mid = right again. The loop will run infinitely.
  3. We will not keep track of a possible value to avoid edge cases. For an array like the one below the left and right will converge on the last element and since left < right : the while loop will be invalid, missing the last True value as a potential Value. Instead of the potentail value we can return the index of either left or right since. 
      4. [FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE]
    1. False: Left = mid + 1 When the middle is on the last False, you will end up on the True side.
    2. True: Right = mid will not move to the False Side
  4. Another Edge case: if there is only one input the loop will never execute as left == right.
    5. bools = [True] 
# one element in bools
# while loop will not execute 
return right if bools[right] == True else -1

Implementation

  1. Since we are on a False we discard all the items to the left.
    2. image
  2. Since we are on a True, we can disregard all the values to the right: they are not the first True element. We keep the True we are on in the possible range by setting by right = mid.
    3. image
  3. Now, we are on another iteration. We disregard all the elements to its right and update the possible value. After this loop, while left < right will not be true, so we can return either the left or right pointer as the First True value.
    1. We won't track a potential value with this approach, as we did previously in 🔑Find the First True in a Sorted Boolean Array , as this leaves room for various edge cases.

image

Code


class Solution:
    def firstTrue(self, bools):

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

        while left < right:

            mid = left + (right - left) // 2

            if bools[mid]:
                right = mid
            else:
                left = mid + 1

        return right if bools[right] == True else -1

SandBox PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

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

Logo
YouTubeDiscord