LeetCode 33 Search in Rotated Sorted Array - Problem Statement

A sorted array was rotated at some pivot. Given this rotated array nums and a target, return the index of target or -1 if not found.

With nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, the answer is 4. The original sorted array [0, 1, 2, 4, 5, 6, 7] was rotated, and 0 now sits at index 4.

Standard binary search won't work directly. How can you adapt it when the array is only partially sorted?

Constraints: $1 \le n \le 5000$. All values unique. Must run in $O(\log n)$.