Find an Element in a Bitonic Array

A bitonic array is strictly increasing up to a peak and strictly decreasing after it. Given a bitonic array of distinct integers and a value k, return the index of k, or an empty OptionalInt if it is not present (OptionalInt is a container that holds one int or nothing). The solution should run in O(log n).

Example

Text

Input:  [-3, 8, 9, 20, 17, 5, 1], k = 20            Output: 3
Input:  [5, 6, 7, 8, 9, 10, 3, 2, 1], k = 30        Output: empty

Brute force: linear scan

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt search(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == k) {
                return OptionalInt.of(i);
            }
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(search(new int[] {-3, 8, 9, 20, 17, 5, 1}, 20) + " " + search(new int[] {5, 6, 7, 8, 9, 10, 3, 2, 1}, 30));
    }
}

Output

OptionalInt[3] OptionalInt.empty

Time: O(n). Space: O(1).

Optimal: find the peak, then search both sides

Find the peak with binary search. If nums[mid] < nums[mid + 1], mid is on the rising part, so the peak is to the right. Otherwise mid is the peak or on the falling part, so the peak is at mid or to the left.
Binary search the rising part nums[0..peak] (inclusive) in ascending order.
If k was not there, binary search the falling part nums[peak + 1..n - 1] in descending order.

Arrays.binarySearch(array, from, to, key) searches the half-open range [from, to) of an ascending array. It returns the index when found, and a negative number otherwise. It cannot search a descending range, so searchDescending flips the comparison: when nums[mid] > k, the target lies to the right.

Java

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static int findPeak(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[mid + 1]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    // Binary search in the descending range nums[from, to). Returns the index or -1.
    static int searchDescending(int[] nums, int from, int to, int k) {
        int lo = from;
        int hi = to - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == k) {
                return mid;
            } else if (nums[mid] > k) {
                lo = mid + 1; // larger values come first, so k is to the right
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    static OptionalInt search(int[] nums, int k) {
        if (nums.length == 0) {
            return OptionalInt.empty();
        }
        int peak = findPeak(nums);
        int i = Arrays.binarySearch(nums, 0, peak + 1, k); // ascending part
        if (i >= 0) {
            return OptionalInt.of(i);
        }
        int j = searchDescending(nums, peak + 1, nums.length, k);
        return j >= 0 ? OptionalInt.of(j) : OptionalInt.empty();
    }

    public static void main(String[] args) {
        int[] a = {-3, 8, 9, 20, 17, 5, 1};
        System.out.println(search(a, 20) + " " + search(a, 5) + " " + search(a, -3));
        System.out.println(search(new int[] {5, 6, 7, 8, 9, 10, 3, 2, 1}, 30));
        System.out.println(search(new int[] {1, 2, 3}, 3) + " " + search(new int[] {3, 2, 1}, 1));
    }
}

Output

OptionalInt[3] OptionalInt[5] OptionalInt[0]
OptionalInt.empty
OptionalInt[2] OptionalInt[2]

Time: O(log n): three binary searches. Space: O(1).

Arrays.binarySearch on a range with a descending order would give an undefined result, so the descending side uses the hand-written loop.

Edge cases

Purely increasing or decreasing: the peak is the last or first index, and one of the two searches covers the whole array.
Single element: the peak is index 0.
Duplicates: the problem guarantees none. With equal neighbours, nums[mid] < nums[mid + 1] cannot tell which side the peak is on.