Number Range (First and Last Position of a Key in a Sorted Array)

Number Range is a Modified Binary Search problem solved with two biased binary searches. One search is biased toward the left to find the first occurrence of the key, and the other is biased toward the right to find the last occurrence. Each search, after finding the key, does not stop but continues shrinking the window toward the desired side, giving an overall O(log n) solution.

What is the problem?

Number Range (First and Last Position of a Key in a Sorted Array). Given an array of numbers sorted in ascending order, find the range, meaning the first and last index, of a given key. If the key is not present, return minus one for both. Explain how two biased binary searches find the two ends.

How does the approach work?

We write a helper search(arr, key, findFirst). It binary-searches normally, but when arr[mid] == key it records mid as a candidate and, instead of returning, it keeps searching: if findFirst is true it sets end = mid - 1 to look further left, otherwise it sets start = mid + 1 to look further right. The other comparisons are standard: key < arr[mid] moves end left, key > arr[mid] moves start right. For example, when finding the first index, if (arr[mid] == key) { result = mid; end = mid - 1; }.

We call this helper twice: once with findFirst = true for the left end and once with findFirst = false for the right end. If the first search returns minus one the key is absent and we return the pair minus one and minus one; otherwise we return the two recorded indices. For the array 1, 3, 3, 3, 5 and key 3, the first search returns index 1 and the second returns index 3.

A senior nuance is that this is strictly O(log n) because each of the two searches is logarithmic, which is better than finding one occurrence and then linearly expanding outward, which could be O(n) when the key fills most of the array. The bias is the whole trick. Complexity is O(log n) time and O(1) space.

What is the banking use case?

The code defines an AuditRangeService exposing range(amounts, key) returning an int array of two indices. A Demo finds the block for a repeated transaction amount and logs the first and last index.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/audit/service/AuditRangeService.java ───
package com.bank.audit.service;

import java.util.logging.Logger;

// Finds the first and last index of an amount in a sorted array.
public class AuditRangeService {
    private static final Logger log = Logger.getLogger(AuditRangeService.class.getName());

    public int[] range(int[] amounts, int key) {
        int first = search(amounts, key, true);
        if (first == -1) {
            log.warning(() -> "Amount " + key + " not present");
            return new int[]{-1, -1};
        }
        int last = search(amounts, key, false);
        log.info(() -> "Amount " + key + " spans indices " + first + " to " + last);
        return new int[]{first, last};
    }

    private int search(int[] arr, int key, boolean findFirst) {
        int start = 0, end = arr.length - 1, result = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (key < arr[mid]) end = mid - 1;
            else if (key > arr[mid]) start = mid + 1;
            else {
                result = mid;                 // record candidate
                if (findFirst) end = mid - 1;  // bias left
                else start = mid + 1;          // bias right
            }
        }
        return result;
    }
}

// ─── File: src/main/java/com/bank/audit/AuditRangeApplication.java ───
package com.bank.audit;

import com.bank.audit.service.AuditRangeService;
import java.util.Arrays;
import java.util.logging.Logger;

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

    public static void main(String[] args) {
        AuditRangeService service = new AuditRangeService();
        int[] amounts = {1000, 3000, 3000, 3000, 5000};
        log.info("Range of 3000: " + Arrays.toString(service.range(amounts, 3000)));
    }
}

What is the project structure?

audit-range-service/
├── pom.xml
├── src/
│   ├── main/
│   │   ├── java/com/bank/audit/
│   │   │   ├── AuditRangeApplication.java        (main class)
│   │   │   └── service/
│   │   │       └── AuditRangeService.java
│   │   └── resources/
│   │       └── application.yml
│   └── test/
│       └── java/com/bank/audit/
│           └── AuditRangeServiceTest.java

How do you build and run?

# Build
mvn clean package -DskipTests

# Run
java -jar target/audit-range-service-1.0.0.jar

# See both biased searches at FINE level
java -Djava.util.logging.ConsoleHandler.level=FINE \
  -jar target/audit-range-service-1.0.0.jar

What is the step-by-step walkthrough?

Input: amounts 1000, 3000, 3000, 3000, 5000 and key 3000.

Oct 27, 2026 9:18:40 PM com.bank.audit.service.AuditRangeService range
INFO: Amount 3000 spans indices 1 to 3
INFO: Range of 3000: [1, 3]

What is the high-level design?

  ═══ HLD — Audit Transaction Range (Banking) ═══

  ┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
  │ Audit Tool │──────→│ API Gateway  │─────→│ Audit Range Svc ×2  │
  └────────────┘       │ (JWT, rate)  │      │ (Spring Boot)       │
                       └──────────────┘      └─────────┬───────────┘
                                                      │ load sorted txns
                                                      ▼
                                           ┌─────────────────────┐
                                           │ PostgreSQL txns      │
                                           └─────────────────────┘

What is the low-level design?

  ═══ LLD — Number Range ═══

  ┌─ Design Patterns Used ──────────────────────────────────┐
  │  Two biased binary searches (left bias, right bias)      │
  │     WHY: both ends in O(log n), no linear expansion      │
  └──────────────────────────────────────────────────────────┘

  ┌─ SOLID Principles Applied ──────────────────────────────┐
  │  S: service only computes the index range                │
  │  O: shared helper parameterized by bias                  │
  │  D: depends only on primitive int array                  │
  └──────────────────────────────────────────────────────────┘

  ── Class Diagram ──────────────────────────────────────────
  ┌──────────────────────────────────────┐
  │ AuditRangeService                     │
  │ ───────────────────────────────────── │
  │ + range(amounts, key): int[]          │
  │ - search(arr, key, findFirst): int    │
  └──────────────────────────────────────┘

  ── State: candidate index + bias direction ───────────────
  on match: record mid, keep shrinking chosen side

  Contract for range(amounts, key):
    Pre:  amounts ascending
    Post: {first, last} indices, or {-1,-1} if absent

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.