LC 33. Search in Rotated Sorted Array

The problem

Solution - $O(\log(n))$ Time

Even after doing 153. Find Minimum in Rotated Sorted Array, a slightly easier variant, this one was difficult. The trick is to identify which side of the array is sorted relative to min. If the left is increasing from left to mid, then we focus on that, if its increasing from mid to right we focus there. The next step is to check if target exists in whichever half we chose. If so, close the window around that by moving left or right appropriately relative to mid.

So why is that tricky? Well it feels redundant to handle two cases that could both send the pointers in either direction, but there is an important reason for this. By checking if target is within the sorted segment, the efficiency of binary search is guaranteed meaning that the only way to confidently cut off one half of our possible nums is to verify that target isn't in a range of strictly increasing nums. If the rotation point is within the range we are looking at, this becomes impossible to check. Take the example [4, 5, 6, 7, 8, 1, 2]. From the first mid, 7, it is impossible to check if target is within the right segment but easy to check if it is within the left. Alternatively, its easy to check if our target is not in the strictly increasing section which is why we then handle the opposite case as an else.

Notably, the first condition nums[left] <= nums[mid] includes where left is equal to mid because the calculation of mid uses Math.floor. Because of this, if there are only two numbers in the array, mid will always move toward the left direction. If it was allowed to equal right while calculating mid with Math.floor, cases would be missed where the the right pointer starts on the target, such as [3, 1] where target = 1.

function search(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((right + left) / 2)
    if (nums[mid] === target) {
      return mid
    }

    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }

  return -1
}