Find in Mountain Array

class Solution {
public:
    int searchInMountain(int key, MountainArray &mA) {
        int n = mA.length();  // Get the length

        // Locate the peak in the mountain
        int start = 1, end = n - 2;
        while (start < end) {
            int mid = (start + end) / 2;
            if (mA.get(mid) < mA.get(mid + 1)) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        int peak = start;
        
        // Try finding the target in the ascending part
        start = 0, end = peak;
        while (start < end) {
            int middle = (start + end) / 2;
            if (mA.get(middle) < key) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }
        if (mA.get(start) == key) {
            return start;
        }
        
        // If not found, search the descending part
        start = peak + 1, end = n - 1;
        while (start < end) {
            int middle = (start + end) / 2;
            if (mA.get(middle) > key) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }
        if (mA.get(start) == key) {
            return start;
        }

        // Return -1 if target is not found
        return -1;
    }
};

The solution provided addresses the task of finding a specified element (key) in a "mountain array" (an array that is first strictly increasing and then strictly decreasing). This solution is written in C++ and operates in two main phases: finding the peak of the array and performing a binary search in the strict parts.

Here's how the solution tackles the problem:

1. Identify the peak of the mountain array: This is done using binary search between the indices 1 and n-2 (where n is the length of the array). The search checks if the middle element is less than its following element to decide the direction of the search.

2. Binary search on the ascending part: Once the peak is determined, another binary search is performed from the start of the array up to the peak to find the key in the increasing sequence.

3. Binary search on the descending part: If the key is not found in the ascending part, the search continues in the descending part (from one element past the peak to the end of the array).

4. Return the index or -1: If the key is found in either part, the corresponding index is returned. If the key is not present in the array, -1 is returned as per the conventions.

Important Implementation Points:

• The function mA.get(i) is presumably a method to get the i-th element of the MountainArray instance mA.
• This implementation ensures that the array accesses are confined within the bounds by carefully selecting the range for the binary searches.
• The use of binary search in both parts of the array ensures that the solution is efficient, ideally running in O(log n) time complexity due to the logarithmic nature of binary search.

This solution is optimal for large datasets due to its logarithmic time complexity and is straightforward in its approach, utilizing the properties of the mountain array effectively.

class Solution {
    public int searchMountain(int targetValue, MountainArray mountainData) {
        int mountainSize = mountainData.length();

        int start = 1;
        int end = mountainSize - 2;
        while (start != end) {
            int mid = (start + end) / 2;
            if (mountainData.get(mid) < mountainData.get(mid + 1)) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        int peak = start;

        start = 0;
        end = peak;
        while (start != end) {
            int mid = (start + end) / 2;
            if (mountainData.get(mid) < targetValue) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        if (mountainData.get(start) == targetValue) {
            return start;
        }

        start = peak + 1;
        end = mountainSize - 1;
        while (start != end) {
            int mid = (start + end) / 2;
            if (mountainData.get(mid) > targetValue) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        if (mountainData.get(start) == targetValue) {
            return start;
        }

        return -1;
    }
}

The Java solution implements a method searchMountain to search for a specific value in a "mountain" array, where the array first increases to a peak and then decreases. The approach leverages binary search in three distinct phases:

1. Identifying the peak of the mountain array.
2. Performing a binary search on the increasing segment of the array from the start to the peak.
3. Performing a binary search on the decreasing segment of the array from the peak to the end.

Initially, the peak is located by comparing middle elements until the highest is found, effectively finding the point where the increase in values stops. Once the peak is identified, two binary searches are conducted:

• The first binary search occurs from the beginning of the array to the peak. This search is optimized for an ascending order.
• The second binary search is carried out from the peak to the end of the array, focusing on a descending order.

Each phase checks whether the target value matches the middle element; if so, the index is immediately returned. If the value is not found in either segment, the method returns -1, indicating the value does not exist in the array.

This structured approach ensures the solution is efficient, taking advantage of the mountain array's properties to reduce the potential search space, thus enhancing performance.

int searchMountainArray(int target, MountainArray *mountainArray) {
    int arrayLength = length(mountainArray);

    // Locate the peak of the mountain array
    int left = 1;
    int right = arrayLength - 2;
    while (left != right) {
        int mid = (left + right) / 2;
        if (get(mountainArray, mid) < get(mountainArray, mid + 1)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    int peak = left;

    // Search the ascending part of the mountain array
    left = 0;
    right = peak;
    while (left != right) {
        int mid = (left + right) / 2;
        if (get(mountainArray, mid) < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // Verify if the target is in the ascending part
    if (get(mountainArray, left) == target) {
        return left;
    }

    // Search the descending part of the mountain array
    left = peak + 1;
    right = arrayLength - 1;
    while (left != right) {
        int mid = (left + right) / 2;
        if (get(mountainArray, mid) > target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // Verify if the target is in the descending part
    if (get(mountainArray, left) == target) {
        return left;
    }

    // If the target is not found in any part
    return -1;
}

The "Find in Mountain Array" algorithm in C is designed to search for a target value in a "mountain array". A mountain array is an array where the sequence begins with an ascending order followed by a descending order. The steps include locating the peak and then searching in the ascending and descending parts independently:

1. Determine the length of the mountain array to identify the bounds for searching.

2. Locate the peak of the array. Initiate left and right pointers to frame the search space, excluding the very first and last elements to avoid unnecessary comparisons. Using a while loop, adjust these pointers by comparing elements at mid-points until the peak is identified.

3. Search for the target in the ascending part of the array using a similar binary search method. Adjust the left and right pointers based on whether the mid-value is less than or equal to the target.

4. If the target is found in the ascending part, return the index immediately.

5. If not found, begin searching in the descending part post the peak. Implement binary search here as well but with conditions reversed to accommodate the descending order.

6. If the target is found in the descending part, return its index.

7. If after both searches the target remains unfound, return -1 indicating the target is not present in the array.

This optimal approach reduces the search space logarithmically and efficiently locates the target in both the ascending and descending segments of the mountain array.

var searchMountainArray = function(targetValue, arr) {
    const arrLength = arr.length();

    let start = 1, end = arrLength - 2;
    while (start !== end) {
        const mid = (start + end) / 2;
        if (arr.get(mid) < arr.get(mid + 1)) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    const peakPoint = start;

    start = 0, end = peakPoint;
    while (start != end) {
        const mid = (start + end) / 2;
        if (arr.get(mid) < targetValue) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    if (arr.get(start) === targetValue) {
        return start;
    }

    start = peakPoint + 1, end = arrLength - 1;
    while (start != end) {
        const mid = (start + end) / 2;
        if (arr.get(mid) > targetValue) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    if (arr.get(start) === targetValue) {
        return start;
    }

    return -1;
}

The algorithm in JavaScript aims to find a specified target value in a "mountain array", which is an array that increases to a peak then decreases. Here's the sequential breakdown of how the solution tackles the problem:

1. Determine the peak of the mountain array:

   • The function searchMountainArray accepts the targetValue and an array arr.
   • Determines the length of the array and initializes two pointers, start and end, to find the mountain peak.
   • A loop continues until start matches end. Inside the loop, compute mid index and adjust the start or end depending on the comparison of arr.get(mid) and arr.get(mid + 1) to locate the peak.

2. Search in the increasing part of the array:

   • Once the peak is found, reset start to the beginning of the array and end to the peak.
   • Perform a binary search in this half by adjusting the start and end pointers based on comparisons of arr.get(mid) to the targetValue, aiming to find the targetValue.

3. Search in the decreasing part if not found in the increasing part:

   • If the target value isn't found in the increasing part, search in the decreasing part.
   • Reset start to the index after the peak and end to the end of the array.
   • Adjust the start and end pointers similar to the binary search but tailored to the decreasing nature of this subarray.

4. Conclude with final checks:

   • Check if the value at start matches the targetValue for both increasing and decreasing parts of the array after the binary search loops.
   • Return the position of the target if found. If not, return -1 indicating the target is not present in the array.

The use of binary search in both halves of the mountain array ensures that the solution remains efficient even for large arrays. This algorithm runs in O(log n) time complexity due to the binary search approach, making it highly effective for sorted arrays with this specific "mountain" structure.

class Solution:
    def searchTargetInMountain(self, target: int, mountainArray: 'MountainArray') -> int:
        arr_len = mountainArray.length()

        # Locate peak of the mountain
        start = 1
        end = arr_len - 2
        while start != end:
            mid = (start + end) // 2
            if mountainArray.get(mid) < mountainArray.get(mid + 1):
                start = mid + 1
            else:
                end = mid
        peak = start

        # Search in ascending segment
        start = 0
        end = peak
        while start != end:
            mid = (start + end) // 2
            if mountainArray.get(mid) < target:
                start = mid + 1
            else:
                end = mid
        if mountainArray.get(start) == target:
            return start
        
        # Search in descending segment
        start = peak + 1
        end = arr_len - 1
        while start != end:
            mid = (start + end) // 2
            if mountainArray.get(mid) > target:
                start = mid + 1
            else:
                end = mid
        if mountainArray.get(start) == target:
            return start

        # If the target is not found
        return -1

The given Python code implements a method to find a target value within a "mountain array". A mountain array is defined by its values first increasing to a peak, then decreasing - resembling a mountain.

The solution involves multiple steps:

1. First, determine the peak of the mountain array. This is done using a binary search to find the point where the transition from increasing to decreasing values occurs. The search starts from the second element and ends at the penultimate element, effectively narrowing down the peak's position.

2. Next, perform binary search in the ascending part of the array (from the start to the peak). If the target value is found in this segment, its index is returned immediately.

3. If the target is not found in the ascending part, search the descending part of the array (from the peak to the end). This search is also conducted using binary search but with a modified condition suitable for a decreasing sequence.

4. If the target is still not located in either segment, return -1, indicating that the target is not present in the mountain array.

Consider the efficiency of this approach: by implementing binary search in both the ascending and descending parts of the array, the solution ensures a time complexity of O(log n), making it highly efficient for large data sets. This methodology is precise and leverages the unique mountainous structure for a fast search.