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

Problems
1

https://algo.monster/problems/binary_search_boundary

2 Likes
2

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

1 Like
3

boilerplate code is missing for C++

4

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

5

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.

6

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?

7

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

8

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)

9

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.

10

There is c++ boiler plate code.

11

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 :stuck_out_tongue:

12

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.

13 
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
}
14

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 :slight_smile:

15

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?

16

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
17

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

18

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)
19

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;

20

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