Bitonic Array Search

Bitonic array search finds a target in an array that strictly increases up to a peak and then strictly decreases. Such an array is called bitonic.

Example:

[1, 3, 8, 12, 9, 5, 2]

The array increases to a maximum at index $3$ , then decreases.

Problem

Given a bitonic array $A$ of length $n$ and a value $x$ , find an index $i$ such that

A[i] = x

If no such index exists, return $-1$ .

Key Idea

A bitonic array consists of two monotone parts:

increasing segment
decreasing segment

The algorithm proceeds in three steps:

Find the peak index
Binary search in the increasing part
Binary search in the decreasing part

Step 1: Find Peak

The peak is the maximum element.

find_peak(A):
    l = 0
    r = length(A) - 1

    while l < r:
        m = l + (r - l) // 2

        if A[m] < A[m + 1]:
            l = m + 1
        else:
            r = m

    return l

Step 2 and 3: Search Both Sides

Perform binary search:

ascending order on left side
descending order on right side

binary_search(A, x, l, r, ascending):
    while l <= r:
        m = l + (r - l) // 2

        if A[m] == x:
            return m

        if ascending:
            if A[m] < x:
                l = m + 1
            else:
                r = m - 1
        else:
            if A[m] < x:
                r = m - 1
            else:
                l = m + 1

    return -1

Full Algorithm

bitonic_search(A, x):
    peak = find_peak(A)

    i = binary_search(A, x, 0, peak, true)
    if i != -1:
        return i

    return binary_search(A, x, peak + 1, length(A) - 1, false)

Example

Let

A = [1, 3, 8, 12, 9, 5, 2]

and

x = 9

Steps:

Peak index = $3$ with value $12$
Search left: not found
Search right: found at index $4$

Correctness

The peak divides the array into two monotone segments.

Left segment is strictly increasing
Right segment is strictly decreasing

Binary search works on each segment independently.

The peak finding algorithm correctly identifies the maximum by comparing adjacent elements. It preserves the invariant that the peak lies within the current interval.

Combining these steps ensures that if $x$ exists, it will be found.

Complexity

phase	time
peak finding	$O(\log n)$
left search	$O(\log n)$
right search	$O(\log n)$
total	$O(\log n)$

Space:

O(1)

Notes

Requires strict bitonic structure
Can be extended to allow equal values with minor changes
Useful in optimization problems and peak detection

Use Cases

Searching in mountain arrays
Signal processing
Optimization landscapes
Competitive programming problems

Implementation

def bitonic_search(a, x):
    def find_peak(a):
        l, r = 0, len(a) - 1
        while l < r:
            m = l + (r - l) // 2
            if a[m] < a[m + 1]:
                l = m + 1
            else:
                r = m
        return l

    def binary_search(a, x, l, r, asc):
        while l <= r:
            m = l + (r - l) // 2
            if a[m] == x:
                return m
            if asc:
                if a[m] < x:
                    l = m + 1
                else:
                    r = m - 1
            else:
                if a[m] < x:
                    r = m - 1
                else:
                    l = m + 1
        return -1

    peak = find_peak(a)

    i = binary_search(a, x, 0, peak, True)
    if i != -1:
        return i

    return binary_search(a, x, peak + 1, len(a) - 1, False)

func BitonicSearch(a []int, x int) int {
    findPeak := func(a []int) int {
        l, r := 0, len(a)-1
        for l < r {
            m := l + (r-l)/2
            if a[m] < a[m+1] {
                l = m + 1
            } else {
                r = m
            }
        }
        return l
    }

    binarySearch := func(a []int, x, l, r int, asc bool) int {
        for l <= r {
            m := l + (r-l)/2
            if a[m] == x {
                return m
            }
            if asc {
                if a[m] < x {
                    l = m + 1
                } else {
                    r = m - 1
                }
            } else {
                if a[m] < x {
                    r = m - 1
                } else {
                    l = m + 1
                }
            }
        }
        return -1
    }

    peak := findPeak(a)

    if i := binarySearch(a, x, 0, peak, true); i != -1 {
        return i
    }

    return binarySearch(a, x, peak+1, len(a)-1, false)
}