Rotated Sorted Array

A sorted array after rotation

Take the sorted array [1, 3, 5, 7, 9] and move several elements from the beginning to the end. For example, it becomes [5, 7, 9, 1, 3]. The global order is broken, but one important property remains: relative to any midpoint, at least one of the two halves is sorted in the usual way.

First identify the sorted half

static int searchRotated(int[] values, int target) {
    int left = 0;
    int right = values.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (values[mid] == target) {
            return mid;
        }

        if (values[left] <= values[mid]) {
            if (values[left] <= target && target < values[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (values[mid] < target && target <= values[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

If values[left] <= values[mid], the left half is sorted. We can then check whether target falls inside its value range. If it does, we keep the left part; otherwise, we move right. The logic is symmetric when the right half is sorted.

Why the complexity stays logarithmic

At every step, roughly half of the current range is still discarded, so the search takes O(log n) time. The extra work consists only of a few boundary comparisons.