You can just as easily use the vanilla binary search code from the previous section, and simply convert the array of booleans into an array of integers (in Python):
arr_bool = [False, False, True, True, True]
arr = list(map(int, arr_bool))
this solution to the next level find the first true :
false true true false false false false true
1
Simple and crisp solution in Java without any fancy coding.
public static int findBoundary(List arr) {
int i = 0, n;
int j = n = arr.size();
// check if all the elements are true
if(arr.get(0) == true && arr.get(n-1) == true){
return 0;
}
// check if all elements are false
if(arr.get(0) == false && arr.get(n-1) == false){
return -1;
}
while(i < j){
int mid = i + (j-i)/2;
// check for true
if(arr.get(mid) == true){
// check for leftmost true
if(mid - 1 >= 0){
if(arr.get(mid - 1) == true){
j = mid - 1;
}
else if(arr.get(mid - 1) == false){
return mid;
}
}else{
j = mid - 1;
}
}
// check for false
if(arr.get(mid) == false){
// check for rightmost true
if(mid + 1 < n){
if(arr.get(mid + 1) == false){
i = mid + 1;
}
else if(arr.get(mid + 1) == true){
return mid + 1;
}
}else{
i = mid + 1;
}
}
}
return -1;
}
Feel free to criticise my code.
We can keep the vanilla binary search and also not use another variable.
My solution is:
function findBoundary(arr) {
let left =0,
right = arr.length - 1
while(left <= right){
let mid = left + Math.floor((right - left) / 2)
if(arr[mid] === true){
right = mid - 1
}else{
left = mid + 1
}
}
return left > arr.length - 1 ? -1 : left;
}
This is a clean alternative approach. It adds an extra check only.
When arr[mid] is True and left == right, the search range has only 1 element and this is the leftmost True we’re searching.
When arr[mid] is True and left != right, let’s continue the search by including the middle element (right = mid).
def find_boundary(arr: List[bool]) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid]:
if left == right:
return mid
else:
right = mid
else:
left = mid + 1
return -1
Yeah, I did the same. All the tests passed so I’m assuming it’s ok
Here is my solution.
int find_boundary(std::vector arr)
{
// WRITE YOUR BRILLIANT CODE HERE
int left = 0;
int right = arr.size()-1;
if((arr.size()==1) && (arr.at(0) == true))
{
return 0;
}else{return -1;}
while(left <= right)
{
int mid=left+(right-left)/2;if((mid ==0) && (arr.at(mid) == true)) return mid; if(arr.at(mid) == true) { if(arr.at(mid-1)==true) { right = mid-1; }else { return mid; } }else { left = mid+1; } } return -1;}
Yeah this is what I did as well. More intuitive IMO
Recursive Code for same logic in Java :
public static int findBoundary(List<Boolean> arr) {
int boundaryIndex = -1;
boundaryIndex = bsUtil(arr, 0, arr.size()-1, boundaryIndex);
return boundaryIndex;
}
public static int bsUtil(List<Boolean> arr, int start, int end, int boundaryIndex){
if (start > end){
return boundaryIndex;
}
int mid = start + (end-start)/2;
if (arr.get(mid)){
return bsUtil(arr, start, mid-1, mid);
} else {
return bsUtil(arr, mid+1, end, boundaryIndex);
}
}
Here is a better easy-understanding code. It also has time complexity O(log n).
def find_boundary(arr: List[bool]) -> int:
# WRITE YOUR BRILLIANT CODE HERE
l = 0
r = len(arr)-1
while l<r:
m = (l+r)//2
if arr[m] == False:
l+=1
else:
r = m
if arr[l]==True:
return l
else:
return -1