Find the First True in a Sorted Boolean Array
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 First True in a Sorted Boolean Array of the right section, i.e., the index of the first true element. If there is no true element, return -1.
Input: arr = [false, false, true, true, true]
Output: 2
Explanation: The first true's index is 2.
Try it yourself
Explanation
The binary decision we must 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 firsttruealthough there may be othertrueto 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 currently recorded leftmost true's index. 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.
Time Complexity: O(log(n))
Space Complexity: O(1)
Implementation
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)
211import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int findBoundary(List<Boolean> arr) {
8 int left = 0;
9 int right = arr.size() - 1;
10 int boundaryIndex = -1;
11 while (left <= right) {
12 int mid = left + (right - left) / 2;
13 if (arr.get(mid)) {
14 boundaryIndex = mid;
15 right = mid - 1;
16 } else {
17 left = mid + 1;
18 }
19 }
20 return boundaryIndex;
21 }
22
23 public static List<String> splitWords(String s) {
24 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
25 }
26
27 public static void main(String[] args) {
28 Scanner scanner = new Scanner(System.in);
29 List<Boolean> arr = splitWords(scanner.nextLine()).stream().map(v -> v.equals("true")).collect(Collectors.toList());
30 scanner.close();
31 int res = findBoundary(arr);
32 System.out.println(res);
33 }
34}
351using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int FindBoundary(List<bool> arr)
8 {
9 int left = 0;
10 int right = arr.Count - 1;
11 int boundaryIndex = -1;
12 while (left <= right)
13 {
14 int mid = (left + right) / 2;
15 if (arr[mid])
16 {
17 boundaryIndex = mid;
18 right = mid - 1;
19 }
20 else
21 {
22 left = mid + 1;
23 }
24 }
25 return boundaryIndex;
26 }
27
28 public static List<string> SplitWords(string s)
29 {
30 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
31 }
32
33 public static void Main()
34 {
35 List<bool> arr = SplitWords(Console.ReadLine()).Select(bool.Parse).ToList();
36 int res = FindBoundary(arr);
37 Console.WriteLine(res);
38 }
39}
401"use strict";
2
3function findBoundary(arr) {
4 let left = 0;
5 let right = arr.length - 1;
6 let boundaryIndex = -1;
7
8 while (left <= right) {
9 const mid = Math.floor((left + right) / 2);
10 if (arr[mid]) {
11 boundaryIndex = mid;
12 right = mid - 1;
13 } else {
14 left = mid + 1;
15 }
16 }
17 return boundaryIndex;
18}
19
20function splitWords(s) {
21 return s === "" ? [] : s.split(" ");
22}
23
24function* main() {
25 const arr = splitWords(yield).map((v) => v === "true");
26 const res = findBoundary(arr);
27 console.log(res);
28}
29
30class EOFError extends Error {}
31{
32 const gen = main();
33 const next = (line) => gen.next(line).done && process.exit();
34 let buf = "";
35 next();
36 process.stdin.setEncoding("utf8");
37 process.stdin.on("data", (data) => {
38 const lines = (buf + data).split("\n");
39 buf = lines.pop();
40 lines.forEach(next);
41 });
42 process.stdin.on("end", () => {
43 buf && next(buf);
44 gen.throw(new EOFError());
45 });
46}
471#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int find_boundary(std::vector<bool> arr) {
9 int left = 0;
10 int right = arr.size() - 1;
11 int boundary_index = -1;
12 while (left <= right) {
13 int mid = left + (right - left) / 2;
14 if (arr.at(mid)) {
15 boundary_index = mid;
16 right = mid - 1;
17 } else {
18 left = mid + 1;
19 }
20 }
21 return boundary_index;
22}
23
24template<typename T>
25std::vector<T> get_words() {
26 std::string line;
27 std::getline(std::cin, line);
28 std::istringstream ss{line};
29 ss >> std::boolalpha;
30 std::vector<T> v;
31 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
32 return v;
33}
34
35int main() {
36 std::vector<bool> arr = get_words<bool>();
37 int res = find_boundary(arr);
38 std::cout << res << '\n';
39}
401use std::error;
2use std::io;
3
4fn find_boundary(arr: Vec<bool>) -> i32 {
5 let mut left = 0;
6 let mut right = arr.len();
7 while left < right {
8 let mid = left + (right - left) / 2;
9 if arr[mid] {
10 right = mid;
11 } else {
12 left = mid + 1;
13 }
14 }
15 if left == arr.len() {
16 -1
17 } else {
18 left as i32
19 }
20}
21
22fn main() -> Result<(), Box<dyn error::Error>> {
23 let mut line = String::new();
24 io::stdin().read_line(&mut line)?;
25 let arr = line.split_whitespace().map(|v| v == "true").collect();
26 let res = find_boundary(arr);
27 println!("{}", res);
28 Ok(())
29}
301package main
2
3import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 "strings"
9)
10
11func findBoundary(arr []bool) int {
12 left := 0
13 right := len(arr) - 1
14 boundaryIndex := -1
15 for left <= right {
16 mid := (left + right) / 2
17 if arr[mid] {
18 boundaryIndex = mid
19 right = mid - 1
20 } else {
21 left = mid + 1
22 }
23 }
24 return boundaryIndex
25}
26
27func splitWords(s string) []string {
28 if s == "" {
29 return []string{}
30 }
31 return strings.Split(s, " ")
32}
33
34func main() {
35 scanner := bufio.NewScanner(os.Stdin)
36 arr := []bool{}
37 scanner.Scan()
38 for _, x := range splitWords(scanner.Text()) {
39 v, _ := strconv.ParseBool(x)
40 arr = append(arr, v)
41 }
42 res := findBoundary(arr)
43 fmt.Println(res)
44}
451def find_boundary(arr)
2 left = 0
3 right = arr.length - 1
4 boundary_index = -1
5 while left <= right
6 mid = (left + right) / 2
7 if arr[mid]
8 boundary_index = mid
9 right = mid - 1
10 else
11 left = mid + 1
12 end
13 end
14 boundary_index
15end
16
17if __FILE__ == $0
18 arr = gets.split.map { |x| x == 'true' }
19 res = find_boundary(arr)
20 puts(res)
21end
221import Data.Array (Array)
2import Data.Array.IArray (bounds, listArray)
3import qualified Data.Array.IArray as A
4
5findBoundary :: Array Int Bool -> Int
6findBoundary arr = uncurry (search (-1)) $ bounds arr
7 where
8 search b l r
9 | l > r = b
10 | arr A.! m = search m l (pred m)
11 | otherwise = search b (succ m) r
12 where
13 m = l + (r - l) `div` 2
14
15main :: IO ()
16main = do
17 arr' <- map (== "true") . words <$> getLine
18 let arr = listArray (0, length arr' - 1) arr'
19 let res = findBoundary arr
20 print res
21The good thing about this approach is that we don't have to modify the while-loop logic in the vanilla binary search from the last module, except for introducing a variable.
Alternative approach
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
Summary
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.