Bitonic Point

JavaView on GFG

Intuition

Find the peak element in a bitonic (first increasing then decreasing) array. Binary search.

Algorithm

1Binary search: if arr[mid] > arr[mid+1]: peak in left half (inclusive). Else: in right half.

Common Pitfalls

•Guaranteed single peak. Binary search on the inflection point. Edge: first or last element.

Bitonic Point.java

Java

// Approach: Binary search. Find the peak element where arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1].
// Time: O(log n) Space: O(1)
class Solution {
    public int findMaximum(int[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if mid is the bitonic point
            if (mid > 0 && mid < n - 1) {
                if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
                    return arr[mid];
                else if (arr[mid] < arr[mid + 1]) // Move right (increasing part)
                    left = mid + 1;
                else // Move left (decreasing part)
                    right = mid - 1;
            } else {
                // Edge case: peak at boundaries
                if (mid == 0)
                    return Math.max(arr[mid], arr[mid + 1]);
                if (mid == n - 1)
                    return Math.max(arr[mid], arr[mid - 1]);
            }
        }

        // According to the question, exactly one bitonic point exists, so this won't be
        // reached.
        return -1;
    }
}

Was this solution helpful?