Given a sorted integer array, nums, and an integer value, target, the array is rotated by some arbitrary number. Search and return the index of target in this array. If the target does not exist, return -1.

search-in-rotated-sorted-array.js

export function binarySearchRotated(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  if (nums.length === 0) {
    // nothing to do if the array is empty
    return -1;
  }

  // iteration stops once low gets larger than high (we only increase low and we only decrease high)
  while (low <= high) {
    // find mid index in between two indexes
    const mid = Math.floor((low + high) / 2);

    // if mid is our element, return its index
    if (nums[mid] === target) {
      return mid;
    }

    if (nums[low] < nums[mid]) {
      // we see that left half is sorted
      if (target < nums[mid] && target >= nums[low]) {
        // we see that target is in the left half, so shift our search there
        high = mid - 1;
      } else {
        // target is not in the left half, so discard it
        low = mid + 1;
      }
    } else {
      // right half is sorted (also it handles case when low === mid === high)
      if (target > nums[mid] && target <= nums[high]) {
        // target is in the right half, so shift our search there
        low = mid + 1;
      } else {
        // target is not in the right half, discard it
        high = mid - 1;
      }
    }
  }

  return -1;
}