101
0/320
Loading content...
A bitonic sequence (also known as a mountain array) is a sequence of distinct integers that exhibits the following unique structural property:
p (where 0 < p < n - 1) such that:
arr[0] < arr[1] < ... < arr[p]arr[p] > arr[p + 1] > ... > arr[n - 1]Visually, if you were to plot the elements on a graph, they would form a single mountain with one summit.
You are provided with a mountain array mountainArr and a target value. Your objective is to determine the smallest index at which the target value appears in the array. If the target value does not exist anywhere in the array, return -1.
Since the target may appear in both the ascending and descending portions of the mountain, and we require the minimum index, you should prioritize searching the ascending (left) side first. Only if the target is not found there should you search the descending (right) side.
A naive linear scan would work but is suboptimal. Leverage the sorted nature of both halves of the mountain to achieve logarithmic search performance. An optimal solution should identify the peak and then perform targeted searches on each half.
mountainArr = [1,2,3,4,5,4,2]
target = 32The value 3 exists at index 2 in the ascending portion of the mountain array. Even though binary search could potentially find elements in the descending side, index 2 is the first (and only) occurrence, so we return 2.
mountainArr = [0,1,2,4,2,1]
target = 3-1The value 3 does not exist anywhere in the mountain array. After searching both the ascending portion [0,1,2,4] and the descending portion [4,2,1], the target is not found, so we return -1.
mountainArr = [1,3,5,4,2]
target = 52The value 5 is the peak element of the mountain array, located at index 2. Since the peak is part of both conceptual halves, it is found during the ascending portion search.
Constraints