# First True in a Sorted Boolean Array - Binary Search / Overview

1 Like

What if check in the first ‘if’ like this
if (arr[mid] && mid == 0 || arr[mid] && !arr[mid - 1])
return mid;
Is it ok?

boilerplate code is missing for C++

Thank you for pointing out. We will add it later!

With the alternative approach, once we make the 3 modifications, at the end the value of ‘right’ is the answer. No need for additional variable. The reason is ‘right’ always pointed to a potential boundary. Also, a better check for len==1 case is returning -1 when arr[-1]==False, which works for len==1 and other len where it’s all False.

Ignore my previous comment, stick with the author’s suggested solution of keeping a variable for result.

After doing more binary search problems, I found keeping a variable for the result to be the best general strategy. This approach can handle all variants, which is nice because we do not need to reason about choices like: 1) lo <= hi or lo < hi?, 2) hi = mid-1 or hi = mid & lo = mid+1 or lo = mid?

Should we add another quick if-check for the situation where mid is already correct
if (midmid === n) return mid
if(mid
mid < n) {
left = mid + 1
res = mid
} else {
right = mid - 1
}

Why does line 6 of the Javascript example `let mid = Math.trunc((left + right) / 2); ` does NOT have the `left +` like in previous and later exercises where I see: `let mid = left + Math.trunc((right - left) / 2)`

The maximum integer in Javascript is `Number.MAX_SAFE_INTEGER = 9007199254740991 = 2^53-1` which is very big and almost impossible for overflow, so either case is fine.

There is c++ boiler plate code.

sorry we had a server issue earlier and the production server was showing the older commit which didn’t have C++. It’s fixed now Consider adding a test case similar to
false true true true true

I had originally thought there would be no way where I would need to look at the left sub array but that is not true because if the true appears one less than the mid index then the answer is “wrong”. I passed all the tests without ever modifying the right variable.
Also, if possible, consider adding an overflow test for left + right/2 since it would force the users to always use the left + (right-left)/2 improvement.

``````func findBoundary(arr []bool) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left+(right-left)/2
if arr[mid] == false { left = mid + 1 } else { right = mid - 1 }
}
if left == len(arr) { return -1 }
return left
}
``````

I am confused as to how the alternative approach would work for a case such as: “true true” which should be a valid case. Setting right to mid would lead to infinite loop so would you need some check for the case when array size is 2 as well?

Here is my current implementation of the alternative approach described in the documentation but it does fail the case of “true true”

function find_boundary(arr) {
let left = 0;
let right = arr.length - 1;

``````while (left < right) {
let mid = left + Math.floor((right - left)/2);
if (arr[mid]){
right = mid;
} else {
left = mid + 1;
}
}

return arr[right]? right: -1;
``````

}
any help would be appreciated I came up with this without reading the article…but I’m not sure if my solution is worse?

def find_boundary(arr: List[bool]) → int:
# Define our left bound
left = 0

``````# Start iterating array backwards
for right in range(len(arr)-1,-1,-1):
# If we find a True on the right side
if arr[right]:
# Start iterating from left until we reach right pointer
while arr[left] != True or left <= right:
# If we find a True, return its index
if arr[left] == True:
return left
# If not, keep looking
left += 1
# If after all that, we didn't find one on the left,
# just return the right index
return right

return -1
``````

I’m pretty sure its worse time than binary search but not sure?

def find_boundary(arr: List[bool]) → int:
left = 0
right = len(arr) - 1

``````if all(arr):
return 0
if not any(arr):
return -1

while left <= right:
mid = (left + right) // 2
if arr[mid]:
return mid
left = mid + 1
``````

Simple for loop approach that passes all cases
for i in range(len(arr)):
if arr[i] == True:
return i
return -1

my recursive solution:

def find_boundary_rec(arr, left, right, location):
if left > right:
return location

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

if arr[mid]:
location = mid
return find_boundary_rec(arr, left, mid - 1, location)
else:
return find_boundary_rec(arr, mid + 1, right, location)
``````

def find_boundary(arr: List[bool]) → int:

``````return find_boundary_rec(arr, 0, len(arr) - 1, -1)
``````

C#, when the boundaries converge, we’ll have a single item collection. Check it’s value and return index if true. Otherwise, constrict the boundary.

if (src.Count == 0) { return -1; }
var (l, h) = (0, src.Count - 1);
while (l <= h)
{
var mid = l + (h - l) / 2;
if (l == h && src[mid]) { return mid; }
(l, h) = src[mid] ? (l, mid) : (mid + 1, h);
}
return -1;

my version of the ‘alernative solution’… kept the <= but added two conditions for success/loop exit

left, right = 0, len(arr)-1
while left <= right:
if (arr[right] == True and arr[right-1] == False) or (arr[right] == True and left == right):
return right

``````    midpoint = (left + right)//2

if arr[midpoint] == False:
left = midpoint + 1
elif arr[midpoint] == True:
right = midpoint
return -1
``````