--- Difficulty: Easy Source: 160 Days of Problem Solving (BONUS PROBLEMS 🎁) Tags: - Arrays - Searching --- # 🚀 _2. Bitonic Point_ 🧠 The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/searching-bonus-problems/problem/maximum-value-in-a-bitonic-array3001) ## 💡 **Problem Description** Given an array of integers `arr[]` that is first strictly increasing and then maybe strictly decreasing, find the bitonic point, which is the maximum element in the array. A **Bitonic Point** is a point before which elements are strictly increasing and after which elements are strictly decreasing. ## 🔍 Example Walkthrough **Input:** ``` arr[] = [1, 2, 4, 5, 7, 8, 3] ``` **Output:** ``` 8 ``` **Explanation:** Elements before 8 are strictly increasing `[1, 2, 4, 5, 7]` and elements after 8 are strictly decreasing `[3]`. **Input:** ``` arr[] = [10, 20, 30, 40, 50] ``` **Output:** ``` 50 ``` **Explanation:** Elements before 50 are strictly increasing `[10, 20, 30, 40]` and there are no elements after 50. **Input:** ``` arr[] = [120, 100, 80, 20, 0] ``` **Output:** ``` 120 ``` **Explanation:** There are no elements before 120, and elements after 120 are strictly decreasing `[100, 80, 20, 0]`. ### Constraints: - $3 \leq arr.size() \leq 10^5$ - $1 \leq arr[i] \leq 10^6$ ## 🎯 **My Approach** ### Step-by-Step: 1. **Problem Understanding:** - The array is bitonic, meaning it has a single peak, with elements strictly increasing up to that point and strictly decreasing afterward. - The task is to find the bitonic point (the maximum value of the array). 2. **Binary Search Approach:** - Since the array has a strict increase followed by a strict decrease, we can use **binary search** to find the bitonic point in **O(log n)** time. - The idea is to find the middle element and compare it with its neighbors: - If the middle element is smaller than its next neighbor, the peak lies on the right side. - If the middle element is greater than its next neighbor, the peak lies on the left side or at the middle element itself. 3. **Steps:** - Initialize `lo = 0` and `hi = arr.size() - 1`. - While `lo < hi`: - Calculate `mid = lo + (hi - lo) / 2`. - If `arr[mid] < arr[mid + 1]`, move `lo = mid + 1` (since the peak is on the right). - If `arr[mid] > arr[mid + 1]`, move `hi = mid` (since the peak is either at `mid` or to the left). - Finally, return `arr[lo]` which will be the maximum element. ## 🕒 **Time and Auxiliary Space Complexity** - **Expected Time Complexity:** O(log n), where `n` is the size of the array. The algorithm uses binary search, which divides the search space in half at each step. - **Expected Auxiliary Space Complexity:** O(1), as the solution uses only a constant amount of additional space (no extra space is required for storing the result or during the search process). ## 📝 **Solution Code** ## Code (C++) ```cpp class Solution { public: int findMaximum(vector &arr) { int lo = 0, hi = arr.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] < arr[mid + 1]) lo = mid + 1; else hi = mid; } return arr[lo]; } }; ``` ## Code (Java) ```java class Solution { public int findMaximum(int[] arr) { int lo = 0, hi = arr.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] < arr[mid + 1]) lo = mid + 1; else hi = mid; } return arr[lo]; } } ``` ## Code (Python) ```python class Solution: def findMaximum(self, arr): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if mid == 0: return max(arr[0], arr[1]) if mid == len(arr) - 1: return max(arr[-1], arr[-2]) if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid+1]: return arr[mid] elif arr[mid] > arr[mid - 1]: lo = mid + 1 else: hi = mid - 1 ``` ## 📢 Contribution and Support For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative! ⭐ If you find this helpful, please give this repository a star! ⭐ ---

📍Visitor Count