Search in Rotated Sorted Array

Binary search a sorted array that was rotated: at every step one half is still sorted, so check whether the target can be inside that half.

The idea

Cutting a rotated array at any mid leaves at least one side with no drop in it, so that side is sorted. If nums[lo] <= nums[mid], the left side is sorted; otherwise the right side is. A sorted range has known bounds, so one comparison tells whether the target can be in it. Search there or throw it away, halving the window every time.

Code

public static int Search(int[] nums, int target) {
    int lo = 0, hi = nums.Length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) { // left half is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else { // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Tips

• Use nums[lo] <= nums[mid], with the =: when lo == mid the left "half" is the single element nums[lo], which counts as sorted.
• Decide using the sorted half only. The other half contains the drop, so its two ends do not bound its values.
• Duplicates break the trick (nums[lo] == nums[mid] == nums[hi] tells you nothing), which pushes the worst case to O(n).

In the .NET library

Array.BinarySearch cannot be used directly because the array is not sorted as a whole. lo + (hi - lo) / 2 avoids the int overflow that (lo + hi) / 2 can hit on huge arrays.