Search in a bitonic array
Filed under Flipkart
Free read 3 of 3Use binary search to find the peak element where arr[i-1] < arr[i] > arr[i+1].
The question
A bitonic array is an array that strictly increases to a peak element and then strictly decreases. Given such an array and a target, find the index of the target in O(log n) time.
Constraints
- Array elements are distinct
- Time complexity must be O(log n)
- n >= 1
Examples
- Input
- arr = [1, 3, 8, 12, 4, 2], target = 4
- Output
- 4
- Why
- The peak is 12. 4 is found in the decreasing part at index 4.
Approach
Use binary search to find the peak element where arr[i-1] < arr[i] > arr[i+1].
Perform standard binary search on the increasing subarray (0 to peak).
If not found, perform binary search on the decreasing subarray (peak+1 to n-1) with reversed logic.
Solution
O(log n) time, O(1) space
class Solution:
def searchBitonic(self, arr, target):
n = len(arr)
l, r = 0, n - 1
while l < r:
mid = (l + r) // 2
if arr[mid] < arr[mid + 1]: l = mid + 1
else: r = mid
peak = l
def bs(lo, hi, rev):
while lo <= hi:
m = (lo + hi) // 2
if arr[m] == target: return m
if (arr[m] < target) ^ rev: lo = m + 1
else: hi = m - 1
return -1
res = bs(0, peak, False)
return res if res != -1 else bs(peak + 1, n - 1, True)
Tips
- What they are testing: Check cases where the target is the peak, at the start, or at the end of the array.
- Common mistake: Searching only one side of the peak or using linear search to find the peak.
Related Flipkart questions
Collected from public candidate posts and coding forums. Updated Nov 2026.