My Java solution using old plain for loop and no right boundary
public static int findBoundary(boolean[] arr) {
//O (log n)
int mid = (arr.length)/2;
int leftBound= 0;
for (int i = 0 ; i<arr.length ; i++){
//corner case
if (arr[0] == true)
return 0;
if(arr[mid] == true)
return mid;
leftBound = mid;
mid= (leftBound+arr.length)/2;
}
return -1;
}
I came up with this solution but idk if its a good one
def find_boundary(arr: List[bool]) → int:
l=0
r=len(arr)-1
if arr[l]==arr[r]:
if arr[l]==True:
return 0
else:
return -1
while(r>=l):
mid=(l+r)//2
if r==l and arr[mid]==True:
return mid
elif r==l and arr[mid]==False:
l+=1
r+=1
elif arr[mid]==True:
r=mid-1
elif arr[mid]==False:
l=mid+1
Can anyone explain why we use Math.trunc() here but Math.floor() for the other questions?
Why can’t I mark this as read?
This is not O(log n). In the worst case, there is no true element indexed thus this would continue to run in the amount of the size of the entire array. Making this in the worse case O(n)
Guys, what do you think about this? Should work a little bit faster for cases when the middle point is right on boundary
function find_boundary(arr) {
let left = 0;
let right = arr.length - 1;
if (arr[0] === true) {
return 0;
}
while (left <= right) {
const mid = Math.floor(left + (right - left)/2);
if (arr[mid] === false && arr[mid+1] === true) {
return mid+1;
}
if (arr[mid] === true && arr[mid - 1] === false) {
return mid;
}
if (mid === true) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
// The alternative approach
int left = 0;
int right = arr.length -1;
while (left <= right)
{
int mid = (left + right)/2;
if (arr[mid] == true)
{
if (mid == right)
return right;
else
right = mid;
}
else
{
left = mid + 1;
}
}
return -1;
My solution:
def find_boundary(arr: List[bool]) → int:
# WRITE YOUR BRILLIANT CODE HERE
if len(arr) == 1 and arr[0] == True: return 0
if len(arr) == 1 and arr[0] == False: return -1
low, high = 0, len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if (arr[mid] == True and mid == 0) or (arr[mid] == True and arr[mid - 1] == False):
return mid
if arr[mid] == False:
low = mid + 1
else:
high = mid - 1
return -1
def find_boundary(arr: List[bool]) -> int:
# WRITE YOUR BRILLIANT CODE HERE
if len(arr) == 1 and arr[0] == True: return 0
if len(arr) == 1 and arr[0] == False: return -1
low, high = 0, len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if (arr[mid] == True and mid == 0) or (arr[mid] == True and arr[mid - 1] == False):
return mid
if arr[mid] == False:
low = mid + 1
else:
high = mid - 1
return -1
can use too
def find_boundary(arr: List[bool]) → int:
# WRITE YOUR BRILLIANT CODE HERE
if len(arr) == 1 and arr[0]: return 0
if len(arr) == 1 and arr[0]: return -1
low, high = 0, len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if (arr[mid] and mid == 0) or (arr[mid] and not arr[mid - 1]):
return mid
if arr[mid] == False:
low = mid + 1
else:
high = mid - 1
return -1
My solution for alternative approach
from typing import List
def find_boundary(arr: List[bool]) → int:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(arr)-1
while left < right:
mid = (left + right) //2
if arr[mid]:
right = mid
else:
left = mid + 1
if arr[left]:
return left
return -1
if name == ‘main’:
arr = [x == “true” for x in input().split()]
res = find_boundary(arr)
print(res)
EZ Clap, just peak the element before mid when mid is true to return early:
public static int findBoundary(boolean[] arr) {
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (arr[mid]) {
if (mid == 0) {
return 0;
}
if (!arr[mid - 1]) {
return mid;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
this is buggy, what happens when
left is INT_MAX - 1
and right is INT_MAX ?
What do you think about my solution :
public static int findBoundary(List<Boolean> arr) {
// WRITE YOUR BRILLIANT CODE HERE
int start=0;
int end=arr.size()-1;
while (start<=end)
{
int midle=end + (start-end) /2;
if(arr.get(midle))
{
// we found the first true
if(midle>0 && !arr.get(midle-1))
{
return midle;
}else if(midle>0 && arr.get(midle))
{
// we found a possible true then move on
// reduce the half
end=midle-1;
}else if(midle==0)
{ //corner case
return 0;
}
}else{
// if is it false then move on
start=midle+1;
}
}
return -1;
}
I believe when someone says time complexity is O(log n) for binary search, they are referring to amortized time (or average time). On interviews worst and best case can also be asked but usually people refer to amortized time
i’m surprised no one is mentioning the recursive version?
Tho I could see the benefit of the while loop - I had to change quite alot from the ‘vanilla’ version if the recursive binary search
function findBoundary(arr, leftI, rightI) {
const halfDifference = Math.floor( Math.abs((rightI - leftI)/2 )); //Math.abs addresses case where arr size is 1
const middle = leftI + halfDifference;
if(arr[leftI]) {
return leftI;
}
if( middle >= arr.length ) {
return -1
}
if( arr[middle] ) {
const newMiddle = arr[middle-1] ? middle-1 : middle;
return findBoundary(arr, leftI+1, newMiddle);
}
return findBoundary(arr, middle+1, rightI);
}
Hey,
Could someone please explain for me, why we suppose that the first boundary_index going to be a first True value in an array to the left’s False? it can be the last one, isn’t it?
Cool 
Got it,
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.
This is out of scope since this example needs to showcase Binary Search, but here’s a short, elegant Python solution:
def find_boundary(arr: List[bool]) -> int:
try:
return arr.index(True)
except ValueError:
return -1
for i in range(len(arr)):
if arr[i]:
return i
return -1