Find in Mountain Array

Efficiently search for a target in a bitonic array using binary search.

binary-search bitonic-array array-traversal

A mountain array is an array that strictly increases to a peak element and then strictly decreases. For example, `[1, 3, 5, 4, 2]` is a mountain array. You are given a mountain array `arr` and a target integer `target`. Your task is to find the index of `target` in the array using an efficient algorithm. If `target` exists in the array, return its index (any valid index). Otherwise, return `-1`. The array is guaranteed to be a mountain array (length >= 3, strictly increasing then strictly decreasing). Implement the function `find_in_mountain(arr, target)` that returns the index of `target` if found, else `-1`. For full efficiency, aim for O(log n) time by combining binary search to find the peak and then binary search on the two sides.

Constraints

- `len(arr) >= 3`
- `arr` is a mountain array (strictly increasing then strictly decreasing).
- `0 <= target <= 10^9`
- Each element of `arr` is an integer in the range `[-10^9, 10^9]`.
- The required time complexity is O(log n), where n is the length of `arr`.

Example

>>> find_in_mountain([1, 3, 5, 4, 2], 4)
3
>>> find_in_mountain([1, 3, 5, 4, 2], 3)
1
>>> find_in_mountain([1, 3, 5, 4, 2], 6)
-1

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

First, find the peak index using a binary search that checks if `arr[mid] < arr[mid+1]`.

After finding the peak, perform a standard binary search on the increasing left part (from 0 to peak).

If not found, perform a binary search on the decreasing right part (from peak to len(arr)-1) with reversed ordering.

Remember to return -1 if neither side contains the target.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.