Search in Rotated Array (Find a Key in a Sorted Array Rotated at an Unknown Pivot)

Search in Rotated Array is a Modified Binary Search problem. A sorted array rotated at an unknown pivot is no longer globally sorted, but at every step at least one half, either left of the middle or right of it, is still sorted. We detect which half is sorted, check whether the key lies within that sorted half's range, and discard the other half accordingly. This keeps the search logarithmic.

What is the problem?

Search in Rotated Array (Find a Key in a Sorted Array Rotated at an Unknown Pivot). Given an ascending sorted array that has been rotated at some unknown pivot, find the index of a given key in O(log n). Explain how, at each step, one half of the array is always sorted and how that lets you decide which half to keep.

How does the approach work?

We binary-search with start and end. At each step mid = start + (end - start) / 2; if arr[mid] == key we return mid. To decide which half is sorted, we compare arr[start] with arr[mid]: if arr[start] <= arr[mid] the left half is sorted, otherwise the right half is sorted. If the left half is sorted and the key lies between arr[start] and arr[mid] we move end = mid - 1, else start = mid + 1. Symmetrically, if the right half is sorted and the key lies between arr[mid] and arr[end] we move start = mid + 1, else end = mid - 1. For example, if (arr[start] <= arr[mid]) { if (key >= arr[start] && key < arr[mid]) end = mid - 1; else start = mid + 1; }.

The key realisation is that a rotation creates exactly one break point, so any middle index always has at least one side without a break, which is the sorted side. Checking the key against that sorted side's clean range is an exact decision with no ambiguity.

A senior nuance is handling duplicates: if arr[start], arr[mid], and arr[end] are all equal we cannot tell which side is sorted, so we shrink both ends by one, degrading to O(n) in the worst case for arrays with heavy duplication; for the distinct-values version the comparisons are decisive and the search stays logarithmic. Complexity is O(log n) time with distinct values and O(1) space.

What is the banking use case?

The code defines a SettlementSearchService exposing indexOf(seqNumbers, key) returning the index or minus one. A Demo searches a rotated array of sequence numbers and logs the index.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/settle/service/SettlementSearchService.java ───
package com.bank.settle.service;

import java.util.logging.Logger;

// Searches a sorted array rotated at an unknown pivot (distinct values).
public class SettlementSearchService {
    private static final Logger log = Logger.getLogger(SettlementSearchService.class.getName());

    public int indexOf(int[] seq, int key) {
        int start = 0, end = seq.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (seq[mid] == key) {
                final int found = mid;
                log.info(() -> "Key " + key + " found at index " + found);
                return mid;
            }
            if (seq[start] <= seq[mid]) {               // left half is sorted
                if (key >= seq[start] && key < seq[mid]) end = mid - 1;
                else start = mid + 1;
            } else {                                     // right half is sorted
                if (key > seq[mid] && key <= seq[end]) start = mid + 1;
                else end = mid - 1;
            }
        }
        log.warning(() -> "Key " + key + " not found");
        return -1;
    }
}

// ─── File: src/main/java/com/bank/settle/SettlementSearchApplication.java ───
package com.bank.settle;

import com.bank.settle.service.SettlementSearchService;
import java.util.logging.Logger;

public class SettlementSearchApplication {
    private static final Logger log = Logger.getLogger(SettlementSearchApplication.class.getName());

    public static void main(String[] args) {
        SettlementSearchService service = new SettlementSearchService();
        int[] seq = {70, 80, 90, 10, 20, 40, 60}; // rotated at midnight
        log.info("Index of settlement seq 20: " + service.indexOf(seq, 20));
    }
}

What is the project structure?

settlement-search-service/
├── pom.xml
├── src/
│   ├── main/
│   │   ├── java/com/bank/settle/
│   │   │   ├── SettlementSearchApplication.java  (main class)
│   │   │   └── service/
│   │   │       └── SettlementSearchService.java
│   │   └── resources/
│   │       └── application.yml
│   └── test/
│       └── java/com/bank/settle/
│           └── SettlementSearchServiceTest.java

How do you build and run?

# Build
mvn clean package -DskipTests

# Run
java -jar target/settlement-search-service-1.0.0.jar

# See half-detection at FINE level
java -Djava.util.logging.ConsoleHandler.level=FINE \
  -jar target/settlement-search-service-1.0.0.jar

What is the step-by-step walkthrough?

Input: seq 70, 80, 90, 10, 20, 40, 60 and key 20.

Oct 27, 2026 10:25:33 PM com.bank.settle.service.SettlementSearchService indexOf
INFO: Key 20 found at index 4
INFO: Index of settlement seq 20: 4

What is the high-level design?

  ═══ HLD — Rotated Settlement Sequence Search (Banking) ═══

  ┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
  │ Settle Ops │──────→│ API Gateway  │─────→│ Settlement Search×3 │
  └────────────┘       │ (JWT, rate)  │      │ (Spring Boot)       │
                       └──────────────┘      └─────────┬───────────┘
                                                      │ load seq batch
                                                      ▼
                                           ┌─────────────────────┐
                                           │ PostgreSQL settles   │
                                           └─────────────────────┘

What is the low-level design?

  ═══ LLD — Search in Rotated Array ═══

  ┌─ Design Patterns Used ──────────────────────────────────┐
  │  Binary search with sorted-half detection                │
  │     WHY: one half is always sorted → exact range decision│
  └──────────────────────────────────────────────────────────┘

  ┌─ SOLID Principles Applied ──────────────────────────────┐
  │  S: service only searches the rotated array              │
  │  O: any rotation amount works unchanged                  │
  │  D: depends only on primitive int array                  │
  └──────────────────────────────────────────────────────────┘

  ── Class Diagram ──────────────────────────────────────────
  ┌──────────────────────────────────────┐
  │ SettlementSearchService               │
  │ ───────────────────────────────────── │
  │ + indexOf(seq, key): int              │
  └──────────────────────────────────────┘

  ── State: [start,end] + which half is sorted ─────────────
  seq[start] <= seq[mid] ? left sorted : right sorted

  Contract for indexOf(seq, key):
    Pre:  distinct values, ascending then rotated
    Post: index of key, or -1

What is the time and space complexity?

Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.

What are common mistakes?

Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.

What are the edge cases?

Edge cases include empty input, single element input, all identical elements, and boundary values.

What should a senior engineer know?

A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.