You are given an array sorted in ascending order which is rotated at some pivot unknown to you beforehand. Find your target in \$O(log n)\$ which means it should be a binary search. If the value does not exist return
-1
.
The approach I took was to narrow the subset of solutions by using an upper bound infinity
and a lower bound infinity
. I would cut the array in half. If the mid
was less than the target
, the right of the mid
would become the new lower bound and if the high
was less than the current target
the mid
would be the new upper bound.
function findTarget(array, target) {
let lo = 0,
hi = array.length,
limit;
while (lo < hi) {
let mid=Math.floor((hi+lo)/2);
if ((array[mid] < array[0]) === (target < array[0])) {
limit = array[mid]
} else if (target < array[0]) {
limit = Number.NEGATIVE_INFINITY
} else {
limit = Number.POSITIVE_INFINITY
}
if (limit < target) {
lo = mid + 1
} else if (limit > target) {
hi = mid
} else {
return mid
}
}
return -1
}
console.log(findTarget([4, 5, 6, 7, 0, 1, 2], 3))