Shifted Array Search

shiftedArrSearch.js

// A characteristic of a shifted sorted array
// is that if you brake it into two halves,
// at LEAST ONE half is ALWAYS going to be sorted:

// 4 5 6 [7] 0 1 2 -> left side is sorted
// 6 7 0 [1] 2 4 5 -> right side is sorted
// ...
// 5 6 7 [0] 1 2 4 -> both side sorted (pivot === shift)

// This means we can use this informatin to apply a BST strategy without having to look for the pivot
// Time complexity O(logn)
// Space complexity O(1)
function shiftedArrSearch(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start < end) {
    const pivot = Math.floor((start + end) / 2);
    if (nums[pivot] === target) {
      return pivot;
    }

    const leftStart = nums[start];
    const leftEnd = nums[pivot - 1];
    const rightStart = nums[pivot + 1];
    const rightEnd = nums[end];

    // If left side is the sorted side we can safely tell if it might contain the target or not
    // therefore we know if we need to move our search on the left side or on the right side
    if (leftStart < leftEnd) {
      if (target <= leftEnd && target >= leftStart) {
        end = pivot - 1; // search the left side
      } else {
        start = pivot + 1; // search the right side
      }
    } else {
      if (target >= rightStart && target <= rightEnd) {
        start = pivot + 1; // search the right side
      } else {
        end = pivot - 1; // search the left side
      }
    }
  }

  // As we pivot on the lower bound (Math.floor) before giving up
  // we need to check against our upper bound
  // console.log(start, end);
  return target === nums[end] ? end : -1;
}