You are given a sorted array that has been rotated by an unknown amount. Find a target value in logarithmic time.

One of the two halves is always sorted

A sorted array rotated by some amount has exactly one point where the order breaks. Pick any midpoint and split the array there, and that break point can only fall in one of the two halves. The other half therefore contains no break at all, which means it is a plainly sorted range.

That is the whole idea, and stating it before writing any code is what the question is for. Binary search normally works because comparing the target to the midpoint tells you which side to discard. Here that comparison tells you nothing on its own, because the array is not globally ordered. What you can do instead is identify the sorted half, ask whether the target falls between its two endpoints, and discard whichever half the answer rules out. Each step still halves the range, so the bound is still logarithmic.

Choosing the comparison so that low can equal mid

Deciding which half is sorted is done by comparing the element at the low index with the element at the midpoint. If the low element is less than or equal to the midpoint element, the left half is sorted; otherwise the break lies to the left and the right half is sorted.

The operator has to be inclusive, and the reason is the two-element range. When the range holds exactly two elements, integer midpoint arithmetic gives a midpoint equal to the low index, so the low and midpoint elements are the same element. A strict less-than then declares the left half unsorted, sends the search right, and can discard the element that holds the answer. With less-than-or-equal, a one-element left half is correctly treated as sorted, which it trivially is.

int search(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;            // avoids the overflow of (lo + hi) / 2
        if (a[mid] == target) return mid;

        if (a[lo] <= a[mid]) {                   // inclusive: mid may be lo when two remain
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Note that the range test always uses both endpoints of the sorted half, never just the midpoint. Writing if (target < a[mid]) hi = mid - 1 inside the left-sorted branch is the single most common wrong answer here: it is the ordinary binary search step, and it discards the right half even when the target is smaller than everything in the sorted left half and can therefore only be found on the right.

The midpoint is computed as low plus half the width rather than as half the sum, which avoids overflow when the indices are large. It costs nothing and its absence is noticed.

Duplicates destroy the logarithmic guarantee

Now the part that separates a good answer from a complete one. Ask whether the values are distinct. If they are not, the algorithm above breaks, and no repair restores the bound.

Take the array 1, 1, 1, 1, 1, 0, 1 and search for 0. The low element is 1 and the midpoint element is 1, so the comparison says the left half is sorted. It is not: the break is at index 5, in the right half. The range test then asks whether 0 lies between 1 and 1, concludes it does not, and searches right, which here happens to be correct. Reverse the rotation to 1, 0, 1, 1, 1, 1, 1 and the same comparison sends the search right, away from the 0. The comparison has become uninformative, and an uninformative comparison cannot halve anything.

The standard repair is that when the low, midpoint and high elements are all equal, you cannot tell which side the break is on, so you advance the low index by one and try again. That preserves correctness and it makes the worst case linear, because an array of a single repeated value with one different element hidden in it forces you to step one index at a time.

It is worth going one step further and saying that linear is not merely the cost of this repair, it is unavoidable. In an array of all ones with a single zero, every element you have not inspected is equally likely to be the zero, and inspecting any element other than the zero tells you nothing about where it is. No comparison-based method can rule out more than one position per probe, so the worst case is linear for any algorithm. Candidates who claim they can keep the logarithmic bound with duplicates are wrong, and being able to say why rather than just conceding is the strongest available answer.

Finding the pivot first, and when that is the better shape

The alternative is two phases: binary search for the rotation point, then run an ordinary binary search on whichever of the two sorted runs can contain the target. It is also O of log n, it doubles the number of comparisons, and it uses two loops instead of one.

The reason to know it is that the pivot search is a reusable primitive. Finding the minimum element, recovering how many rotations were applied, and answering repeated queries against the same array are all direct consequences of knowing the pivot, and if the interviewer's next question is any of those, the two-phase shape has already done the work. For a single lookup the single-loop version is tighter and easier to argue correct, so state which you are optimising for rather than treating one as canonical.