# Bitonic Array Search

# 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:

1. Find the peak index
2. Binary search in the increasing part
3. Binary search in the decreasing part

## Step 1: Find Peak

The peak is the maximum element.

```id="bit-peak"
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

```id="bit-search"
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

```id="bit-full"
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:

1. Peak index = $3$ with value $12$
2. Search left: not found
3. 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

```id="py-bit"
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)
```

```id="go-bit"
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)
}
```