Minimum Difference Element (Closest Element to a Key in a Sorted Array)

Minimum Difference Element is a Modified Binary Search problem. We binary-search for the key, and if we find it exactly the difference is zero. If we do not find it, the closing window leaves the start pointer just above the key and the end pointer just below it, so the closest element is whichever of those two neighbours has the smaller absolute difference, with ties broken toward the smaller value.

What is the problem?

Minimum Difference Element (Closest Element to a Key in a Sorted Array). Given an array of numbers sorted in ascending order, find the element whose absolute difference from a given key is smallest. If two elements are equally close, return the smaller one. Explain how binary search plus a comparison of the two neighbours around the closing window finds it.

How does the approach work?

We binary-search with start = 0 and end = n - 1. If arr[mid] == key we return arr[mid] immediately, difference zero. The standard moves apply otherwise: key < arr[mid] sets end = mid - 1, key > arr[mid] sets start = mid + 1. When the loop ends with start > end, the key lies between arr[end] and arr[start], so we compare arr[start] - key against key - arr[end] and return the element with the smaller difference. For example, if (arr[start] - key < key - arr[end]) return arr[start]; else return arr[end];.

The reason this works is that binary search, when it fails to find the key, always leaves start pointing at the smallest element greater than the key and end pointing at the largest element smaller than the key, which are exactly the two candidates for the closest element. Using the less-than comparison in that final check means a tie returns arr[end], the smaller value, satisfying the tie-break rule.

A senior nuance is guarding the edges: if the key is smaller than every element, end becomes minus one and we return arr[0]; if the key is larger than every element, start becomes n and we return the last element. Those edge guards are easy to forget. Complexity is O(log n) time and O(1) space.

What is the banking use case?

The code defines a FxQuoteService exposing closestQuote(quotes, target) returning the nearest quote. A Demo finds the nearest quote for a target rate and logs it.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/fx/service/FxQuoteService.java ───
package com.bank.fx.service;

import java.util.logging.Logger;

// Finds the quote closest to a target rate; ties favour the smaller quote.
public class FxQuoteService {
    private static final Logger log = Logger.getLogger(FxQuoteService.class.getName());

    public int closestQuote(int[] quotes, int target) {
        if (target < quotes[0]) return quotes[0];                 // edge: below all
        if (target > quotes[quotes.length - 1]) return quotes[quotes.length - 1]; // above all
        int start = 0, end = quotes.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (quotes[mid] == target) {
                log.info(() -> "Exact quote " + target + " available");
                return quotes[mid];
            }
            if (target < quotes[mid]) end = mid - 1; else start = mid + 1;
        }
        // start straddles above, end straddles below the target
        int closest = (quotes[start] - target < target - quotes[end]) ? quotes[start] : quotes[end];
        log.info(() -> "Closest quote to " + target + " is " + closest);
        return closest;
    }
}

// ─── File: src/main/java/com/bank/fx/FxQuoteApplication.java ───
package com.bank.fx;

import com.bank.fx.service.FxQuoteService;
import java.util.logging.Logger;

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

    public static void main(String[] args) {
        FxQuoteService service = new FxQuoteService();
        int[] quotes = {82, 84, 87, 91, 95}; // INR per USD quotes (scaled)
        log.info("Rajesh SAV2001 nearest quote to 89: " + service.closestQuote(quotes, 89));
    }
}

What is the project structure?

fx-quote-service/
├── pom.xml
├── src/
│   ├── main/
│   │   ├── java/com/bank/fx/
│   │   │   ├── FxQuoteApplication.java           (main class)
│   │   │   └── service/
│   │   │       └── FxQuoteService.java
│   │   └── resources/
│   │       └── application.yml
│   └── test/
│       └── java/com/bank/fx/
│           └── FxQuoteServiceTest.java

How do you build and run?

# Build
mvn clean package -DskipTests

# Run
java -jar target/fx-quote-service-1.0.0.jar

# See the straddle comparison at FINE level
java -Djava.util.logging.ConsoleHandler.level=FINE \
  -jar target/fx-quote-service-1.0.0.jar

What is the step-by-step walkthrough?

Input: quotes 82, 84, 87, 91, 95 and target 89.

Oct 27, 2026 9:44:28 PM com.bank.fx.service.FxQuoteService closestQuote
INFO: Closest quote to 89 is 87
INFO: Rajesh SAV2001 nearest quote to 89: 87

What is the high-level design?

  ═══ HLD — Nearest FX Quote Lookup (Banking) ═══

  ┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
  │ FX Desk UI │──────→│ API Gateway  │─────→│ FX Quote Svc ×2     │
  └────────────┘       │ (JWT, rate)  │      │ (Spring Boot)       │
                       └──────────────┘      └─────────┬───────────┘
                                                      │ load quote board
                                                      ▼
                                           ┌─────────────────────┐
                                           │ PostgreSQL quotes    │
                                           └─────────────────────┘

What is the low-level design?

  ═══ LLD — Minimum Difference Element ═══

  ┌─ Design Patterns Used ──────────────────────────────────┐
  │  Binary search + straddle-neighbour comparison           │
  │     WHY: closest is one of the two pointers on a miss     │
  └──────────────────────────────────────────────────────────┘

  ┌─ SOLID Principles Applied ──────────────────────────────┐
  │  S: service only finds the closest quote                 │
  │  O: any sorted quote board works unchanged               │
  │  D: depends only on primitive int array                  │
  └──────────────────────────────────────────────────────────┘

  ── Class Diagram ──────────────────────────────────────────
  ┌──────────────────────────────────────┐
  │ FxQuoteService                        │
  │ ───────────────────────────────────── │
  │ + closestQuote(quotes, target): int   │
  └──────────────────────────────────────┘

  ── State: on miss start>end straddle target ──────────────
  candidates = quotes[end] (below), quotes[start] (above)

  Contract for closestQuote(quotes, target):
    Pre:  quotes ascending, non-empty
    Post: element with min |value - target|, ties → smaller

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.