Search Bitonic Array (Find a Key in a Rise-Then-Fall Array)

Search Bitonic Array combines two Modified Binary Search ideas. First we find the peak index of the bitonic array. That peak splits the array into an ascending part on the left and a descending part on the right. We binary-search the ascending part normally, and if the key is not there we binary-search the descending part with reversed comparisons. Returning the first match gives the smaller index when the key appears twice.

What is the problem?

Search Bitonic Array (Find a Key in a Rise-Then-Fall Array). Given a bitonic array, strictly increasing then strictly decreasing, find the index of a given key. If the key appears on both sides, return the smaller index. Explain how you first find the peak and then binary-search each side with the correct order.

How does the approach work?

We first find the peak index with the Bitonic Maximum technique, comparing each middle with its right neighbour. Once we have peak, we run a standard ascending binary search over indices 0..peak. If it returns a valid index we return it, because the left side holds the smaller indices. Otherwise we run a descending binary search over indices peak + 1..n - 1, where the comparisons are reversed: key < arr[mid] moves start = mid + 1 and key > arr[mid] moves end = mid - 1. For example, the descending search uses if (key == arr[mid]) return mid; else if (key < arr[mid]) start = mid + 1; else end = mid - 1;.

Returning the left-side match first naturally yields the smaller index when the key exists on both the rising and falling sides. Each of the three phases, finding the peak and the two searches, is logarithmic, so the whole algorithm is logarithmic.

A senior nuance is that the descending search is just an ordinary binary search with the inequality signs flipped, so reusing a single order-aware search routine keeps the code clean. Another nuance is correctly partitioning at the peak so neither search overlaps the other. Complexity is O(log n) time and O(1) space.

What is the banking use case?

The code defines a BitonicSearchService exposing firstIndexOf(prices, key) returning the earliest index or minus one. A Demo searches a bitonic price series for a value present on both sides and logs the earlier index.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/bitonic/service/BitonicSearchService.java ───
package com.bank.bitonic.service;

import java.util.logging.Logger;

// Searches a bitonic array: find peak, then search each monotonic side.
public class BitonicSearchService {
    private static final Logger log = Logger.getLogger(BitonicSearchService.class.getName());

    public int firstIndexOf(int[] prices, int key) {
        int peak = findPeak(prices);
        int left = search(prices, key, 0, peak, true);    // ascending side
        if (left != -1) {
            log.info(() -> "Key " + key + " found on rising side at " + left);
            return left;                                   // smaller index wins
        }
        int right = search(prices, key, peak + 1, prices.length - 1, false); // descending side
        log.info(() -> "Key " + key + " search returned index " + right + " on falling side");
        return right;
    }

    private int findPeak(int[] a) {
        int start = 0, end = a.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (a[mid] > a[mid + 1]) end = mid; else start = mid + 1;
        }
        return start;
    }

    private int search(int[] a, int key, int start, int end, boolean ascending) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (a[mid] == key) return mid;
            if (ascending) {
                if (key < a[mid]) end = mid - 1; else start = mid + 1;
            } else {
                if (key < a[mid]) start = mid + 1; else end = mid - 1; // reversed
            }
        }
        return -1;
    }
}

// ─── File: src/main/java/com/bank/bitonic/BitonicSearchApplication.java ───
package com.bank.bitonic;

import com.bank.bitonic.service.BitonicSearchService;
import java.util.logging.Logger;

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

    public static void main(String[] args) {
        BitonicSearchService service = new BitonicSearchService();
        int[] prices = {101, 119, 140, 135, 119, 104};
        log.info("Earliest index of price 119: " + service.firstIndexOf(prices, 119));
    }
}

What is the project structure?

bitonic-search-service/
├── pom.xml
├── src/
│   ├── main/
│   │   ├── java/com/bank/bitonic/
│   │   │   ├── BitonicSearchApplication.java     (main class)
│   │   │   └── service/
│   │   │       └── BitonicSearchService.java
│   │   └── resources/
│   │       └── application.yml
│   └── test/
│       └── java/com/bank/bitonic/
│           └── BitonicSearchServiceTest.java

How do you build and run?

# Build
mvn clean package -DskipTests

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

# See peak and side searches at FINE level
java -Djava.util.logging.ConsoleHandler.level=FINE \
  -jar target/bitonic-search-service-1.0.0.jar

What is the step-by-step walkthrough?

Input: prices 101, 119, 140, 135, 119, 104 and key 119.

Oct 27, 2026 10:11:55 PM com.bank.bitonic.service.BitonicSearchService firstIndexOf
INFO: Key 119 found on rising side at 1
INFO: Earliest index of price 119: 1

What is the high-level design?

  ═══ HLD — Compliance Price-Point Lookup (Banking) ═══

  ┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
  │ Compliance │──────→│ API Gateway  │─────→│ Bitonic Search ×2   │
  └────────────┘       │ (JWT, rate)  │      │ (Spring Boot)       │
                       └──────────────┘      └─────────┬───────────┘
                                                      │ load price series
                                                      ▼
                                           ┌─────────────────────┐
                                           │ Time-series store    │
                                           └─────────────────────┘

What is the low-level design?

  ═══ LLD — Search Bitonic Array ═══

  ┌─ Design Patterns Used ──────────────────────────────────┐
  │  Peak split + two order-aware binary searches            │
  │     WHY: each half is monotonic and searchable           │
  └──────────────────────────────────────────────────────────┘

  ┌─ SOLID Principles Applied ──────────────────────────────┐
  │  S: findPeak and search each do one job                  │
  │  O: boolean bias reuses one search for both orders       │
  │  D: depends only on primitive int array                  │
  └──────────────────────────────────────────────────────────┘

  ── Class Diagram ──────────────────────────────────────────
  ┌──────────────────────────────────────┐
  │ BitonicSearchService                  │
  │ ───────────────────────────────────── │
  │ + firstIndexOf(prices, key): int      │
  │ - findPeak(a): int                    │
  │ - search(a,key,s,e,ascending): int    │
  └──────────────────────────────────────┘

  ── State: peak index partitions the array ────────────────
  left [0..peak] ascending, right [peak+1..n-1] descending

  Contract for firstIndexOf(prices, key):
    Pre:  prices bitonic
    Post: earliest 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.