2
\$\begingroup\$

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))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.