Leetcode - Search in Rotated Sorted Array

Question

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

This is abinary_search question.

Idea

• Use the regular binary search algorithm
• The trick here is to identify what portion of the array is sorted (where are we)
  • If the left portion of the array is sorted, then M will be ≥ to L (we are in the left)
    • Check to see where the target is is it in the right portion (is target < L or is target > M
    • Otherwise it is in the left portion
  • If the left portion of the array is not sorted then the right portion of the array is sorted (we are in the right)
    • Check to see where the target is is it in the left portion (is target < M or is target > R
    • Otherwise it is in the right portion
• If search fails return -1

Solution