Find in Mountain Array

The key idea

Problem

You are given a mountain array mountainArr and an integer target. Return the minimum index such that mountainArr.get(index) == target. If target is not in the array, return -1.

You cannot access the array directly. You may only ask for an element through the MountainArray interface: mountainArr.get(k) returns the element at index k and mountainArr.length() returns the array's length. A submission that calls get more than 100 times is judged wrong, so a linear scan will not pass — you must use the mountain shape to your advantage.

An array is a mountain if it strictly increases up to a single peak and then strictly decreases. Because both sides are sorted, the answer is reachable with a handful of binary searches instead of touching every element.

Constraints

• 3 <= mountain_arr.length() <= 10^4
• 0 <= target <= 10^9
• 0 <= mountain_arr.get(index) <= 10^9
• More than 100 calls to MountainArray.get is judged Wrong Answer

Examples

Complexity

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

More Binary Search problems

• Binary SearchEASY
• Capacity To Ship Packages Within D DaysMEDIUM
• Find First and Last Position of Element in Sorted ArrayMEDIUM
• Find K Closest ElementsMEDIUM
• Find Minimum in Rotated Sorted ArrayMEDIUM
• Find Peak ElementMEDIUM
• First Bad VersionEASY
• Guess Number Higher or LowerEASY
• Koko Eating BananasMEDIUM
• Lowest Common Ancestor of a Binary Search TreeMEDIUM
• Median of Two Sorted ArraysHARD
• Search a 2D MatrixMEDIUM