Skip to content
Hello Python

Find the First True Boundary

Practice ExerciseInterviewEasyBinary Search

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement find_first_true(flags). flags contains zero or more False values followed by zero or more True values. Return the index of the first True value, or len(flags) when no True value exists.

Starter code

def find_first_true(flags):
    pass
Test cases

interior-boundary

{
  "args": [
    [
      false,
      false,
      true,
      true
    ]
  ]
}

Expected: 2

all-true

{
  "args": [
    [
      true,
      true
    ]
  ]
}

Expected: 0

Wizard outline
  1. Step 1: Create a half-open search interval

    Represent the full candidate range as [0, len(flags)]. Including len(flags) as an answer makes the all-false and empty cases natural.

  2. Step 2: Preserve a true midpoint candidate

    Move right to mid when flags[mid] is True. The midpoint may itself be the first True, so it must remain inside the candidate interval.

  3. Step 3: Represent the all-false sentinel

    Return len(flags) when no True value exists. The half-open upper bound is also the correct answer when the transition never occurs.

  4. Step 4: Converge on an interior boundary

    Alternate both updates until the candidate interval contains one answer. An interior transition requires both branches while preserving the invariant that the first True lies in [left, right].

Footguns and prerequisites
  • Returning -1 for an all-false input violates the required insertion-boundary contract.
  • Using right = mid - 1 mixes closed and half-open bounds and can skip the first true position.
  • arrays strings two pointers sliding window
Reviewed references
Prepared Interview Problems
  • Binary Search a Globally Sorted Matrix(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search two dimensional matrix as a complete Interview Problem.

  • Find a Peak Element(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing find peak element as a complete Interview Problem.

  • First and Last Target Position(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing first last position as a complete Interview Problem.

  • Minimum of a Rotated Sorted Array(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing find minimum rotated as a complete Interview Problem.

  • Peak Index in a Mountain Array(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing peak index mountain array as a complete Interview Problem.

  • Search a Rotated Array With Duplicates(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search rotated array two as a complete Interview Problem.

  • Search a Rotated Sorted Array(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search rotated array as a complete Interview Problem.

  • Search a Row-and-Column Sorted Matrix(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search sorted matrix two as a complete Interview Problem.

  • Time-Based Key-Value Store(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing time based key value store as a complete Interview Problem.

Recommended approach and implementation

A monotone predicate with one boundary is a direct lower-bound search even when the desired item is absent. Every index before left is known false, while every index at or after right is known true or the sentinel len(flags).

Why it works: Each midpoint test preserves the half-open partition: a true midpoint becomes the new possible boundary, while a false midpoint and everything before it are discarded. Convergence leaves left at the first true index or the sentinel.

def find_first_true(flags):
    left, right = 0, len(flags)
    while left < right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid
        else:
            left = mid + 1
    return left