Table of Contents
Problem Description:
Suppose you have an array of integers, mountainArray, which is a mountain array. A mountain array is defined as an array that increases to a peak element and then decreases. You need to find the target element target in the mountain array and return its index. If the target element is not present in the array, return -1.
You can assume that the array has the following properties:
mountainArray.length >= 3- There exists some
iwith0 < i < mountainArray.length - 1such that: mountainArray[0] < mountainArray[1] < ... < mountainArray[i - 1] < mountainArray[i]mountainArray[i] > mountainArray[i + 1] > ... > mountainArray[mountainArray.length - 1]
Sample Input and Expected Output:
Input:
mountainArray = [1, 2, 3, 4, 5, 3, 1]
target = 3
Output:
Index of target element 3: 2
Input:
mountainArray = [1, 2, 3, 4, 5, 3, 1]
target = 6
Output:
Target element 6 not found in the mountain array.
Solution in C++:
We can solve this problem using a modified binary search approach to find the peak element in the mountain array and then perform two binary searches to find the target element in the increasing and decreasing halves of the array.
#include <iostream>
#include <vector>
int findPeakElement(std::vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int binarySearch(std::vector<int>& nums, int target, int left, int right, bool increasing) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (increasing) {
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
if (nums[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
int findInMountainArray(int target, std::vector<int>& mountainArray) {
int peakIndex = findPeakElement(mountainArray);
int targetIndex = binarySearch(mountainArray, target, 0, peakIndex, true);
if (targetIndex == -1) {
targetIndex = binarySearch(mountainArray, target, peakIndex + 1, mountainArray.size() - 1, false);
}
return targetIndex;
}
int main() {
std::vector<int> mountainArray = {1, 2, 3, 4, 5, 3, 1};
int target1 = 3;
int target2 = 6;
int index1 = findInMountainArray(target1, mountainArray);
int index2 = findInMountainArray(target2, mountainArray);
if (index1 != -1) {
std::cout << "Index of target element " << target1 << ": " << index1 << std::endl;
} else {
std::cout << "Target element " << target1 << " not found in the mountain array." << std::endl;
}
if (index2 != -1) {
std::cout << "Index of target element " << target2 << ": " << index2 << std::endl;
} else {
std::cout << "Target element " << target2 << " not found in the mountain array." << std::endl;
}
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(log n), where n is the size of the mountainArray. This is because we perform three binary searches, each taking logarithmic time.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.