Medium

# Find the local minima in a given array

Objec­tive:  Given an array of integers write an algorithm to find the local minima.

Local Minima: An element is considered as local minima if it is less than both of its neighbors (if neighbors exist).

Example:

```int [] arrA = {11, 4, 2, 5, 11, 13, 5};
Output: Local Minima is: 2
int []arrA = {1,2,3,4};
Output: 1
int []arrA = {3};
Output: 3
int []arrA = {6,4};
Output: 4
```

NOTE: There could be many local minima’s, we need to find anyone.\

Approach:

Naïve: Use for loop and compare every element with its neighbor.

Time Complexity – O(n)

Binary Search Approach:

• Check if the mid element is smaller than its left and right neighbors.
• If the left neighbor is less than the mid element then make a recursive call to the left half of the array. (There will be at least one local minima in the left half, take few examples to check)
• If the right neighbor is less than the mid element then make a recursive call to the right half of the array.

Time Complexity – O(logn)

Code:

Output:

Local Minima is: 2

Reference: this