# Find the local minima in a given array

**Objective**: Given an array of integer 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 any one.

**Approach**:

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

Time Complexity – O(n)

**Binary Search Approach:**

- Check if mid element is smaller than its left and right neighbors.
- If 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 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:** http://www.geeksforgeeks.org/find-local-minima-array/**

I’d avoid recursion and do the binary search in a while loop for

– improving the readability and

– traceability and

– avoid long callstacks

causes stack overflow for input array: {11, 2, 2, 5, 11, 1, 5};

i find bug when input has duplicate or has no element is satisfy

why we using binary search?

i think we can’t use binary search because array may not be sorted always