Even though the array is rotated, one half is always sorted. Use this to decide which half to search.
Find mid and check if nums[mid] == target.
Determine which half is sorted by comparing nums[left] with nums[mid].
If left half is sorted (nums[left] <= nums[mid]):
- If target is in range
[nums[left], nums[mid]), search left. - Otherwise search right.
If right half is sorted:
- If target is in range
(nums[mid], nums[right]], search right. - Otherwise search left.