← Flipkart questions

Search in a bitonic array

Filed under Flipkart

Free read 3 of 3

Use 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

  1. Use binary search to find the peak element where arr[i-1] < arr[i] > arr[i+1].

Solution

O(log n) time, O(1) space

Python
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.