Introduction

A bitonic array increases up to one peak and then decreases. That shape lets you search faster than a linear scan because both halves are ordered, just in opposite directions.

The Main Idea

To find the index of a value x in O(log n) time, split the problem into two binary searches:

1. find the peak element in O(log n)
2. binary-search the increasing half
3. binary-search the decreasing half

People often describe this as 2 log n, but asymptotically it is still O(log n) because the constant factor does not change the class.

The key observation is that once you know the peak index, the array becomes two sorted ranges:

• left side: strictly increasing
• right side: strictly decreasing

Binary search works on both as long as you compare in the correct direction.

Finding the Peak

The peak is the index where the array stops rising and starts falling. Because the slope tells you which side to move toward, you can find it with a modified binary search.

1def find_peak(arr):
2    low = 0
3    high = len(arr) - 1
4
5    while low < high:
6        mid = (low + high) // 2
7
8        if arr[mid] < arr[mid + 1]:
9            low = mid + 1
10        else:
11            high = mid
12
13    return low

If arr[mid] is smaller than the next element, you are still on the rising side, so the peak must be to the right. Otherwise you are at the peak or on the falling side, so move left.

Binary Search on Each Side

After locating the peak, search the left side with ordinary ascending-order binary search. If that fails, search the right side with a descending-order variant.

1def binary_search_ascending(arr, low, high, target):
2    while low <= high:
3        mid = (low + high) // 2
4
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            low = mid + 1
9        else:
10            high = mid - 1
11
12    return -1
13
14
15def binary_search_descending(arr, low, high, target):
16    while low <= high:
17        mid = (low + high) // 2
18
19        if arr[mid] == target:
20            return mid
21        if arr[mid] < target:
22            high = mid - 1
23        else:
24            low = mid + 1
25
26    return -1

Notice the reversed comparisons in the descending search. That is the part people most often get wrong.

Full Solution

Now combine the three steps into one function.

1def search_bitonic(arr, target):
2    if not arr:
3        return -1
4
5    peak = find_peak(arr)
6
7    if arr[peak] == target:
8        return peak
9
10    left_result = binary_search_ascending(arr, 0, peak - 1, target)
11    if left_result != -1:
12        return left_result
13
14    return binary_search_descending(arr, peak + 1, len(arr) - 1, target)
15
16
17data = [1, 4, 7, 11, 14, 13, 8, 3]
18print(search_bitonic(data, 14))  # 4
19print(search_bitonic(data, 8))   # 6
20print(search_bitonic(data, 2))   # -1

This solution uses constant extra space and performs a logarithmic number of comparisons.

Why the Complexity Works

The peak search is O(log n). The ascending search is another O(log n), and the descending search is also O(log n). In the worst case you do all three, which is still O(log n).

If you want to be explicit about the arithmetic, the work looks like:

• one peak search
• up to one ascending search
• up to one descending search

That is roughly 3 log n comparisons, which is still logarithmic time.

Edge Cases to Think About

A good implementation should also consider:

• a single-element array
• a peak at the first or last position
• a target equal to the peak
• values not present in the array

If the array is not strictly bitonic, meaning duplicates appear around the top, the logic may need extra handling. The cleanest version of this problem assumes strictly increasing values before the peak and strictly decreasing values after it.

Common Pitfalls

Using ordinary binary search on the decreasing half without reversing the comparison logic returns wrong answers even though the code looks almost correct.

Accessing arr[mid + 1] without maintaining the low < high loop condition can produce an index error near the end of the array.

Forgetting to check whether the peak itself matches the target adds unnecessary work and can hide simple bugs.

Assuming the input is bitonic when it is not can make the algorithm return incorrect results. Validate the problem constraints if the data source is unreliable.

Summary

• Search a bitonic array by first finding the peak with modified binary search.
• Then run binary search on the increasing half and, if needed, on the decreasing half.
• The total time remains O(log n).
• The descending-half search must reverse the usual binary-search comparisons.
• The approach is efficient and uses only O(1) extra space.