🚀 Solving LeetCode 852: Peak Index in a Mountain Array Using Binary Search

📝 Problem Statement:

Given a mountain array, find the peak index. A mountain array is one where:

• The elements first strictly increase, reaching a peak.
• After the peak, they strictly decrease.

You're tasked with finding the index of that peak element.

Example:

Input: arr = [0, 2, 3, 4, 5, 3, 1]
Output: 4

Here, arr[4] = 5 is the peak element.

---

🛠️ Approach:

A brute force approach would involve iterating through the array to find the peak by checking when an element is greater than its neighbors. But we can do better.

Since the array is structured like a mountain, with an increasing part followed by a decreasing part, we can leverage binary search to efficiently solve this problem.

The idea is:

• Use binary search to find the peak.
• If the middle element is greater than the next one (arr[mid] > arr[mid + 1]), this means we're on the descending part of the mountain, so the peak is to the left, including mid.
• Otherwise, the peak is to the right, excluding mid.

This approach runs in O(log n) time, making it much faster than a linear search.

---

🔨 Solution Code:

Here's the code to solve the problem using binary search:

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        // Binary Search loop
        while (start < end) {
            int mid = start + (end - start) / 2;

            // If mid is greater than the next element, peak is on the left
            if (arr[mid] > arr[mid + 1]) {
                end = mid;
            } else {
                // If mid is less than the next element, peak is on the right
                start = mid + 1;
            }
        }
        // Start and end will converge to the peak index
        return start;
    }
}

---

🔍 Explanation:

1. Initial Setup:

   • We define start as 0 and end as the last index of the array.

2. Binary Search:

   • The loop continues until start is equal to end.
   • We calculate mid as the average of start and end.
   • If the middle element is greater than the next one (arr[mid] > arr[mid + 1]), this means we are in the descending part of the mountain. So, we move end to mid, as the peak could still be at mid.
   • Otherwise, we move start to mid + 1, as the peak must be in the right part.

3. Termination:

   • The loop terminates when start == end, and this index is the peak of the mountain.

---

⚡ Time Complexity:

The time complexity of this solution is O(log n), where n is the number of elements in the array. This is because we halve the search space in each step, as binary search does.

---

🎯 Key Takeaways:

• The binary search technique is an efficient way to solve problems when you can leverage the sorted or partially sorted nature of the input.
• Always think about how to reduce time complexity by avoiding brute-force solutions.
• Practice problems like these to improve your algorithmic thinking!