Find in a Mountain List
arr is a mountain: it has at least 3 items, strictly increases up to a single peak that is not at either end, and then strictly decreases. Return the smallest index at which target appears, or -1 if it does not appear at all.
A value can appear at most twice, once on each side of the peak; when it does, return the index on the rising side. Aim for binary search: find the peak first, then search the rising side and, if needed, the falling side.
Example 1
arr [1,3,5,7,6,4,2]
target 4
returns 5
4 appears only once, at index 5 on the falling side.
Example 2
arr [1,3,5,7,6,4,2]
target 3
returns 1
3 is at index 1.
Constraints
3 <= len(arr) <= 100-1000 <= arr[i], target <= 1000arris a valid mountain
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Sorting and searching problems
- Find in a Rotated ListMedium
- H-IndexMedium
- K Closest ValuesMedium
- Kth Smallest Pair SumMedium
- Least Truck CapacityMedium
- Merge IntervalsMedium
- Rebuild the LineMedium
- Smallest Divisor Under a LimitMedium