Open lpatmo opened 5 years ago
function findOnes(arr) {
//choose an arbitrary midpoint (1/2 of array)
//base case: midpoint = 1, and left number is 0
//base case: last element is 0
//base case: first element is 1
//if midpoint is 0, move to right by arr up to midpoint divided by 2
// if midpoint is 1, move to left by arr up to midpoint divided by 2...
let start = 0;
let end = arr.length -1;
let midpoint = Math.floor((start+end)/2);
// console.log(midpoint)
if (arr[midpoint] === 1 && arr[midpoint-1] === 0) {
return arr.length - midpoint;
}
if (arr[arr.length-1] === 0) {
return 0;
}
if (arr[0] === 1) {
return arr.length;
}
//console.log('midpiont initial', midpoint)
//Basically practicing binary search below:
while (start < end) {
if (arr[midpoint] === 1 && arr[midpoint-1] === 0) {
return arr.length - midpoint; //not happy with this, but it's a necessary check
}
if (arr[midpoint] === 0) {
start = midpoint + 1;
} else {
end = midpoint - 1;
}
midpoint = Math.floor((start+end)/2);
}
return arr.length - midpoint;
}
Given a sorted array of 0s and 1s, count the number of ones in the array.
Requirement: Challenge: perform this in O(log(N)) time complexity.