Be the first user to complete this post Login To Mark Completed

0

Add to List Add To List..(Max 5) Close Save

Beginner

Find a peak element in a Given Array

Objective: In this article, we will discuss an algorithm to Find a peak element in a Given Array. We will see the recursion techniques to solve this problem.

Peak Element: peak element is the element that is greater than or equal to both of its neighbors.

Input:  Array, arrA[] .

Output: A peak element and its index

Approach:

A simple approach is to do a linear scan of an array and using a few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?

The answer is yes, by using Binary Search techniques.

• If the middle element is the peak element, return it
• If the middle element is smaller than its left element, we will get our peak element on the left half
• If the middle element is smaller than its right element, we will have our peak element on the right.

Time Complexity : O(logN) 

Notes:

1. If an array has all the same elements, every element is a peak element.
2. Every array has a peak element.
3. The array may have many peak elements but we are finding only one.
4. If the array is in ascending or descending order then the last element or the first element of the array will be the peak element respectively.

Run This Code

Code:

Peak Element is found at index [6] = 5

---

---

Also Read:

- Check if Array is Consecutive Integers Beginner
- Maximizing Contiguous Ones with a Single Flip in a Binary Array Medium
- Check if array is sorted using recursion Beginner
- Adding One to a Number Represented by an Array Medium
- Product of all Unique elements in a given array. Beginner
- Majority Element – Part 1 Beginner
- Find Kth Smallest or Largest element in an Array. Medium
- Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer Hard

---