Search in Rotated Array - Approach

Even though the array is rotated, one half is always sorted. Use this to decide which half to search.

$1.$ Find mid and check if nums[mid] == target.

$2.$ Determine which half is sorted by comparing nums[left] with nums[mid].

$3.$ If left half is sorted (nums[left] <= nums[mid]):

• If target is in range [nums[left], nums[mid]), search left.
• Otherwise search right.

$4.$ If right half is sorted:

• If target is in range (nums[mid], nums[right]], search right.
• Otherwise search left.