⬅ Previous Topic
Search Single Element in Sorted ArrayNext Topic ⮕
Square Root using Binary Search⬅ Previous Topic
Search Single Element in Sorted ArrayNext Topic ⮕
Square Root using Binary SearchTopic Contents
Given an array of integers, your task is to find the index of any peak element in the array.
A peak element is defined as an element that is not smaller than its neighbors. For the edge elements (first or last), we only compare with their one existing neighbor.
If there are multiple peaks, return the index of any one of them. If the array is empty, return -1
.
low = 0
and high = n - 1
.low ≤ high
, calculate mid = (low + high) / 2
.arr[mid]
is a peak:mid
.arr[mid] < arr[mid + 1]
, move to right half: low = mid + 1
.high = mid - 1
.public class PeakElementFinder {
public static int findPeakElement(int[] arr) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
boolean leftOK = (mid == 0 || arr[mid] >= arr[mid - 1]);
boolean rightOK = (mid == arr.length - 1 || arr[mid] >= arr[mid + 1]);
if (leftOK && rightOK) return mid;
else if (mid < arr.length - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid - 1;
}
return -1; // Should never reach here if at least one peak exists
}
public static void main(String[] args) {
int[] arr = {1, 3, 20, 4, 1, 0};
int peakIndex = findPeakElement(arr);
System.out.println("Peak Index: " + peakIndex + ", Peak Element: " + arr[peakIndex]);
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The middle element is a peak in the first check. |
Average Case | O(log n) | At each step, the search space is halved, similar to binary search. |
Worst Case | O(log n) | In the worst case, binary search continues until the peak is found at the edge. |
O(1)
Explanation: The algorithm uses constant extra space regardless of input size.
⬅ Previous Topic
Search Single Element in Sorted ArrayNext Topic ⮕
Square Root using Binary SearchYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.