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
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 infinityinfinity and a lower bound infinityinfinity. I would cut the array in half. If the midmid was less than the targettarget, the right of the midmid would become the new lower bound and if the highhigh was less than the current targettarget the midmid 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))
