The problem requires us to find the index of a given target element in a mountain array. A mountain array is an array that firstly increases and then decreases. We can approach this problem by first finding the index of the peak element in the mountain array. Then we can perform two binary searches - one on the left side of the peak and the other on the right side of the peak to find the target element.
Approach
We can solve this problem in the following steps:
Find the peak element in the mountain array using binary search.
We can start by initializing start = 0 and end = arr.length() - 1 and finding the middle index mid = start + (end - start) / 2.
Then we check if the element at index mid is less than the element at index mid+1.
If this is true, then we know that we are still on the increasing side of the mountain, so we set start = mid + 1.
If this is false, then we know that we are on the decreasing side of the mountain, so we set end = mid.
We continue this until start == end and return the value of start which is the index of the peak element in the mountain array.
Perform two binary searches on the left and right side of the peak to find the target element.
We can set firstTry = orderBinarySearch(mountainArr, target, 0, peak) to search for the target element on the left side of the peak.
If firstTry != -1, we found the target and can return firstTry.
If firstTry == -1, we can perform another binary search on the right side of the peak using orderBinarySearch(mountainArr, target, peak + 1, mountainArr.length() - 1).
We return the result of this binary search.
Implement the orderBinarySearch method to perform a binary search on a given range of the mountain array.
We can use a boolean variable asc to check if the array is in ascending order.
We start with start and end values and perform binary search until start <= end.
At each iteration, we calculate the middle index mid as mid = start + (end - start) / 2.
We check if the element at mid is the target element. If yes, return mid.
If the array is in ascending order, and the target element is less than the element at mid, we know that the target element must be on the left side of mid. So we set end = mid - 1.
If the array is in descending order, and the target element is greater than the element at mid, we know that the target element must be on the left side of mid. So we set end = mid - 1.
If the target element is not found, we return -1.
Complexity
Time complexity:
Time complexity: O(log n), where n is the length of the mountain array.
We use binary search to find the peak element, which takes O(log n) time.
We use two binary searches to find the target element, each taking O(log n) time.
Space complexity: O(1). We use constant extra space throughout the algorithm.
Top comments (0)