Adapting binary search to find an element in a sorted array that has been rotated.
A common interview problem is to search for an element in a sorted array that has been rotated at some unknown pivot point. For example, the sorted array `[0, 1, 2, 4, 5, 6, 7]` might become `[4, 5, 6, 7, 0, 1, 2]`. A naive linear search would take O(n) time. The challenge is to solve this in O(log n) time, which strongly suggests a modification of binary search. The standard binary search logic won't work directly because the entire array is not sorted. However, the key observation is that when we pick a middle element, at least one of the two halves (from `low` to `mid` or from `mid` to `high`) must be sorted. We can determine which half is sorted by comparing `arr[mid]` with `arr[low]`. If `arr[mid] >= arr[low]`, the left half is sorted. Otherwise, the right half is sorted. Once we identify the sorted half, we can check if our `target` lies within the range of that sorted half. If it does, we can discard the other half and continue our search in the sorted portion. If it doesn't, we know the target must be in the unsorted half, so we discard the sorted half and search in the other one. This modified logic allows us to correctly narrow down the search space by half in each step, preserving the O(log n) complexity.