stephencnca
BAN USERbinary search, O(log n)
function solver(array, s) {
var start = s!=undefined?s:0;
if (array.length == 1) {
if (array[0] === 0) {
return start + 1;
} else {
return 0;
}
}
var current = Math.floor(array.length / 2);
if (array[current] === 0) {
if (array[current+1] != undefined && array[current+1] === 1) {
return start+current+1;
} else {
return solver(array.slice(current),start+current);
}
} else {
if (array[current-1] != undefined &&array[current-1] === 0) {
return start+current;
} else {
return solver(array.slice(0,current), start);
}
}
}
with the same example you gave, what if i'm searching for 6? 6 is also smaller than ar[mid], but you won't find 6 at (mid+1, n).
- stephencnca June 24, 2015