Rotated Arrays & Binary Search on Answer Space

Topics Covered:
54. Search in Rotated Sorted Array & Pivot Identification • 55. Binary Search on Monotonic Answer Space (Optimization Problems)

When data deviates from simple linear contiguous ordering—through circular rotation or continuous monotonic function landscapes—binary search retains its logarithmic power through invariant preservation. In circularly shifted arrays, ordering is not destroyed but partitioned into piecewise monotonic segments where at least one half is always strictly sorted. Beyond physical arrays, binary search generalizes into an optimization engine capable of determining optimal capacities, thresholds, and allocations by querying monotonic feasibility predicates $P(x)$. This chapter formalizes circular rotation mechanics, pivot identification, duplicate key degradation, and the transformation of complex minimax optimization problems into binary search on answer spaces.

• Formulate the half-sorted structural invariant of circularly rotated sorted arrays.
• Implement $O(\log n)$ target search across rotated sequences by identifying sorted partitions and testing target inclusion boundaries.
• Develop pivot identification algorithms to locate the minimum element and compute the circular rotation factor $k$.
• Analyze the worst-case degradation to $O(n)$ when handling duplicate elements in rotated arrays and apply duplicate elimination rules.
• Generalize binary search to discrete and continuous monotonic answer spaces via feasibility predicate testing ($P(x)⟹P(x+1)$).
• Apply binary search on answer space to solve canonical optimization problems including ship packaging capacity, allocation of pages, and aggressive cows.

Let $S=[s_0,s_1,\dots ,s_{n-1}]$ be an array of $n$ distinct elements sorted in strictly ascending order such that $s_0<s_1<\cdots <s_{n-1}$. A circular right rotation by $k$ positions ($0\le k<n$) maps each element at index $i$ to index $(i+k)\mathrm{mod}n$. The resulting rotated array $A$ consists of two strictly increasing contiguous subarrays separated by a single point of discontinuity: the pivot element (the minimum element of the array).

The table below illustrates a circular rotation of $S=[0,1,2,4,5,6,7]$ by $k=4$ positions:

In this rotated state, every element in the left partition $A_1=[4,5,6,7]$ is strictly greater than every element in the right partition $A_2=[0,1,2]$. The global minimum element $0$ resides at index $k=4$, which marks the rotation offset.

Standard binary search assumes global monotonicity across $[low,high]$. While a rotated array lacks global monotonicity, it satisfies a pivotal structural invariant:

The Half-Sorted Invariant:
For any arbitrary index $\text{mid}=\lfloor (low+high)/2\rfloor$ within a rotated sorted array $[low,high]$, at least one of the two halves—either $[low,\text{mid}]$ or $[\text{mid},high]$—is guaranteed to be strictly sorted.

Formal Proof:

1. The entire array contains at most one point of descent (the pivot where $A[i]>A[i+1]$).
2. The midpoint $\text{mid}$ divides the interval $[low,high]$ into two disjoint sub-intervals: $[low,\text{mid}]$ and $[\text{mid},high]$.
3. The single point of descent can belong to at most one of these two sub-intervals.
4. Therefore, the sub-interval that does not contain the point of descent contains no inversions and must be strictly sorted.

By comparing the boundary values $A[low]$ and $A[\text{mid}]$, we deterministically classify which half is sorted:

• If $A[low]\le A[\text{mid}]$: The left partition $[low,\text{mid}]$ is monotonically sorted.
• If $A[low]>A[\text{mid}]$: The point of descent lies in the left half; therefore, the right partition $[\text{mid},high]$ is monotonically sorted.

Once the sorted half is identified, determining whether the target resides within its bounds requires a single $O(1)$ range check. If the target falls inside the sorted half, we contract the search window to that half; otherwise, the target must lie in the opposite half.

Consider searching for $\text{target}=0$ in the rotated array $A=[4,5,6,7,0,1,2]$ of size $n=7$:

Total comparisons performed: 3 iterations, achieving logarithmic performance $\lceil {\log }_{2}7\rceil =3$.

FUNCTION SearchRotatedArray(A: Array of Integer, n: Integer, target: Integer) -> Integer:
    low <- 0
    high <- n - 1

    WHILE low <= high DO
        mid <- low + FLOOR((high - low) / 2)

        IF A[mid] = target THEN
            RETURN mid
        END IF

        // Check if the left partition [low..mid] is sorted
        IF A[low] <= A[mid] THEN
            // Left half is sorted; check if target lies within [A[low], A[mid])
            IF A[low] <= target AND target < A[mid] THEN
                high <- mid - 1
            ELSE
                low <- mid + 1
            END IF
        // Otherwise, the right partition [mid..high] must be sorted
        ELSE
            // Right half is sorted; check if target lies within (A[mid], A[high]]
            IF A[mid] < target AND target <= A[high] THEN
                low <- mid + 1
            ELSE
                high <- mid - 1
            END IF
        END IF
    END WHILE

    RETURN -1    // Target not present in array

Complexity Analysis:

• Time Complexity: $O(\log n)$. At each iteration, exactly half of the remaining elements are eliminated from consideration, giving $T(n)=T(n/2)+O(1)⟹O(\log n)$.
• Space Complexity: $O(1)$ auxiliary memory; operates strictly in place with constant pointer variables.

In many applications, we need to locate the pivot index $k$ directly (e.g., to determine how many times an array has been rotated, or to find the minimum value in $O(\log n)$ time).

When searching for the minimum element, we compare $A[\text{mid}]$ directly against the right boundary $A[high]$:

• If $A[\text{mid}]>A[high]$: The minimum element cannot be in $[low,\text{mid}]$; it must reside strictly in $[\text{mid}+1,high]$. Thus, $low\leftarrow \text{mid}+1$.
• If $A[\text{mid}]\le A[high]$: The element at $\text{mid}$ could itself be the minimum, or the minimum lies to the left in $[low,\text{mid}]$. Thus, $high\leftarrow \text{mid}$.
• The loop terminates when $low=high$, pointing directly to the minimum element.

Trace: Finding Minimum in $A=[4,5,6,7,0,1,2]$

The rotation count of the original sorted array is given directly by the pivot index: $\text{rotations}=k=4$.

When an array contains non-distinct duplicate values (e.g., $A=[1,0,1,1,1]$ or $B=[1,1,1,0,1]$), the half-sorted test can fail:

In this scenario, it is impossible to deduce whether the discontinuity lies in the left half or the right half based solely on boundary comparisons:

• In $A=[1,0,1,1,1]$: $A[0]=1,A[2]=1,A[4]=1$. The pivot $0$ is in the left half.
• In $B=[1,1,1,0,1]$: $B[0]=1,B[2]=1,B[4]=1$. The pivot $0$ is in the right half.

Mitigation Strategy:

When $A[low]=A[\text{mid}]=A[high]$, we cannot safely discard half of the array. Instead, we shrink both boundaries inward:

If all elements in the array are identical except for one (e.g., $[1,1,\dots ,0,\dots ,1]$), the algorithm trims one element at each step, degrading time complexity to $O(n)$.

Many advanced algorithmic problems ask for an optimal numerical value rather than searching within a provided array:

• "Find the minimum capacity of a conveyor belt to ship packages within $D$ days."
• "Find the maximum minimum distance between $k$ cows placed in $n$ stalls."
• "Find the minimum reading speed to finish $n$ piles of books within $H$ hours."

These problems belong to the Minimax / Maximin optimization family. Direct constructive solutions are often NP-hard or require complex dynamic programming. However, if the underlying physical problem satisfies Monotonicity, we can invert the question:

The Monotonicity Condition:

Let $P(x)\in \{\text{True},\text{False}\}$ be a validation predicate that checks whether candidate answer $x$ satisfies the problem constraints. A problem exhibits monotonicity over answer space $[\text{min\_val},\text{max\_val}]$ if the predicate forms a single step-function transition:

• Minimization Problems (First True): If capacity $x$ is sufficient, any capacity $x^{\prime }>x$ is also sufficient:
  $$P(x)=\text{True}⟹P(x+1)=\text{True}$$
• Maximization Problems (Last True): If distance $x$ is achievable, any smaller distance $x^{\prime }<x$ is also achievable:
  $$P(x)=\text{True}⟹P(x-1)=\text{True}$$

The table below visualizes the predicate evaluation landscape across a discrete candidate answer space for a minimization problem:

Because the boolean array $[F,F,F,F,T,T,T,T,T,T]$ is monotonically sorted, binary search locates the boundary value $x=5$ in $O(\log (\text{range}))\times \text{Cost}(P)$ time.

Template A: Minimization (First True Pattern)

FUNCTION BinarySearchMinimization(minBound: Integer, maxBound: Integer) -> Integer:
    low <- minBound
    high <- maxBound
    ans <- maxBound            // Fallback upper bound

    WHILE low <= high DO
        mid <- low + FLOOR((high - low) / 2)

        IF IsFeasible(mid) THEN
            ans <- mid         // Candidate answer found; try smaller values
            high <- mid - 1
        ELSE
            low <- mid + 1     // mid is insufficient; increase candidate
        END IF
    END WHILE

    RETURN ans

Template B: Maximization (Last True Pattern)

FUNCTION BinarySearchMaximization(minBound: Integer, maxBound: Integer) -> Integer:
    low <- minBound
    high <- maxBound
    ans <- minBound            // Fallback lower bound

    WHILE low <= high DO
        mid <- low + FLOOR((high - low) / 2)

        IF IsFeasible(mid) THEN
            ans <- mid         // Feasible; try larger values
            low <- mid + 1
        ELSE
            high <- mid - 1    // Infeasible; decrease candidate
        END IF
    END WHILE

    RETURN ans

Problem Statement:

A conveyor belt carries $n$ packages with weights $W=[w_0,w_1,\dots ,w_{n-1}]$ that must be shipped sequentially within $D$ days. Each day, packages are loaded onto a ship in the given order until loading another package would exceed the ship's weight capacity. Determine the minimum ship capacity required to ship all packages within $D$ days.

Numerical Instance:

• Packages: $W=[1,2,3,4,5,6,7,8,9,10]$ ($n=10$, total weight $=55$, max single weight $=10$).
• Deadline: $D=5$ days.

Derivation of Search Space Bounds:

1. Lower Bound ($low$): A ship must at least be able to carry the heaviest individual package:
   $$low=\underset{0\le i<n}{\max }W[i]=10$$
   If $\text{capacity}<10$, package $10$ can never be loaded.
2. Upper Bound ($high$): A single ship carrying all packages in $1$ day requires:
   $$high=\sum _{i=0}^{n-1}W[i]=55$$

Feasibility Predicate ($O(n)$ Greedy Check):

Given a candidate capacity cap, sequentially accumulate weights into the current day. When adding package $w_i$ would exceed cap, dispatch the ship, increment days used by $1$, and start the next day with package $w_i$. If $\text{daysUsed}\le D$, return True; otherwise False.

FUNCTION CanShip(W: Array of Integer, n: Integer, D: Integer, cap: Integer) -> Boolean:
    daysUsed <- 1
    currentDayLoad <- 0

    FOR i <- 0 TO n - 1 DO
        IF currentDayLoad + W[i] > cap THEN
            daysUsed <- daysUsed + 1
            currentDayLoad <- W[i]
        ELSE
            currentDayLoad <- currentDayLoad + W[i]
        END IF
    END FOR

    RETURN daysUsed <= D

Executing binary search over the range $[low=10,high=55]$ with target days $D=5$:

The optimal minimum ship weight capacity is 15, found in exactly 5 predicate evaluations.

The table below summarizes classic algorithmic problems solvable via binary search on monotonic answer space:

1. The Half-Sorted Invariant: In any circularly rotated sorted array, dividing the interval at $\text{mid}$ guarantees that at least one half is strictly sorted. Testing $A[low]\le A[\text{mid}]$ identifies the sorted partition in $O(1)$ time.
2. Boundary Testing for Discard: Once the sorted partition is identified, a single range check ($A[low]\le \text{target}<A[\text{mid}]$ or $A[\text{mid}]<\text{target}\le A[high]$) determines whether the target lies inside the sorted half, enabling $O(\log n)$ search.
3. Pivot & Minimum Element: Comparing $A[\text{mid}]$ with $A[high]$ locates the array's minimum element and rotation factor $k$. If $A[\text{mid}]>A[high]$, the pivot is strictly right; if $A[\text{mid}]\le A[high]$, the pivot is at or left of $\text{mid}$.
4. Duplicate Penalty: When $A[low]=A[\text{mid}]=A[high]$, the sorted half cannot be deduced. Trimming both boundaries ($low++,high--$) preserves correctness but degrades worst-case performance to $O(n)$.
5. Answer Space Monotonicity: When optimization problems ask for "Minimum Capacity" or "Maximum Distance", formulate a verification predicate $P(x)$. If $P(x)$ is monotonic, binary search computes the optimal answer in $O(\text{Cost}(P)\cdot \log (\text{Range}))$ time.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 2 (Getting Started) & Section 12.3. MIT Press.
2. Bentley, J. (2000). Programming Pearls (2nd ed.), Column 4: Writing Correct Programs & Column 9: Code Tuning. Addison-Wesley.
3. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 6.2.1: Searching an Ordered Table. Addison-Wesley.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Chapter 1.4: Analysis of Algorithms (Binary Search on Functions). Addison-Wesley.