Search in Rotated Sorted Array (Bar Raiser Question)

One side remains sorted\n\nUse ordinary binary-search bounds left and right. At each midpoint, return immediately if nums[mid] is the target. With distinct values, either nums[left]..nums[mid] is sorted or nums[mid]..nums[right] is sorted. If the left half is sorted, check whether nums[left] <= target < nums[mid]; keep that half when true, otherwise search the right half. If the right half is sorted, check whether nums[mid] < target <= nums[right]; keep it when true, otherwise search the left half. The invariant is that the target, if present, remains in the retained interval, and the sorted half makes one exclusion certain. Runtime is O(log n) with O(1) space. Test an unrotated array, pivot at either end, target at midpoint, absent target, one element, and values around the pivot. If duplicates are allowed, say the worst case can degrade to O(n) when equal endpoints hide which side is sorted.