Local Minima in Java
An Array
Finding a local minimum in an array a[0. m-1] of different integers is the job. A[i] is considered a local minimum if it is smaller than two of its neighbors.
When comparing corner elements, we only need to take into account one neighbor.
There may be more than one local minimum in an array; we must select one of them.
Examples:
Input: a[] = {18, 15, 13, 3, 14, 14, 15};
result: Index of local minima is 2
Since the result is smaller than both of its neighbors, the index of 13 is printed. Remember that the elements 15 and 14's indexes are likewise acceptable outputs.
Input: a[] = {2, 7, 1, 7, 2};
result: Index of local minima is 2
Input: a[] = {7, 8, 9};
result: Index of local minima is 0
Input: a[] = {9, 8, 7};
result: Index of local minima is 8
Doing a linear scan of the array and returning it as soon as a local minima is discovered is a straightforward approach. The method's worst-case temporal complexity is O. (n).
Binary Search is the foundation of an effective solution. We evaluate the Centre element's neighbors. We return the middle element if it is not bigger than any of its neighbors. There will always be a local minima in the left half if the middle element is larger than its left neighbor (to see why, consider a few examples).There will always be a local minimum in the right half if the central element is larger than its right neighbour (due to same reason as left half).
// A C++ prog to demonstrate a local minima in an array
#include <stdio.h>
// a function that uses binary search and returns the index of a local minima.
int localMinUtil(int a[], int l, int h, int m)
{
// Find the middle element's index.
int mid = l + (h - l)/2; /* (l + h)/2 */
// Compared to its neighbours, the middle element (if neighbours exist)
if ((mid == 0 || a[mid-1] > a[mid]) &&
(mid == m-1 || a[mid+1] > a[mid]))
return mid;
// Left half must include a local minimum if the centre element is not a minima and its left neighbour is smaller than it.
else if (mid > 0 && a[mid-1] < a[mid])
return localMinUtil(a, l, (mid -1), m);
//Right half must include a local minimum if centre element is not a minima and its right neighbour is smaller than it.
return localMinUtil(a, (mid + 1), h, m);
}
// recursive function localMinUtil wrapper ()
int localMin(int a[], int m)
{
return localMinUtil(a, 0, m-1, m);
}
/* Driver application to verify the aforementioned features*/
int main()
{
int a[] = {41, 31, 1, 13, 18, 4};
int m = sizeof(a)/sizeof(a[0]);
printf("Index of a local minima is %d",
localMin(a, m));
return 0;
}Output:
Index of a local minima is 2
Java program
// A Java prog to demonstrate a local minima in an array
import java.io.*;
class LM
{
// a function that uses binary search and returns the index of a local minima.
public static int localMinUtil(int[] a, int l,int h, int m)
{
// Find index of middle element
int mid = l + (h - l) / 2;
// Compared to its neighbours, the middle element (if neighbours exist)
if(mid == 0 || a[mid - 1] > a[mid] && mid == m - 1 ||
a[mid] < a[mid + 1])
return mid;
// Left half must include a local minimum if the centre element is not a minima and its left neighbour is smaller than it.
else if(mid > 0 && a[mid - 1] < a[mid])
return localMinUtil(a, l, mid - 1, m);
// Right half must include a local minimum if centre element is not a minima and its right neighbour is smaller than it.
return localMinUtil(a, mid + 1, h, m);
}
//recursive function localMinUtil wrapper ()
public static int localMin(int[] a, int m)
{
return localMinUtil(a, 0, m - 1, m);
}
public static void main (String[] args)
{
int a[] = {44, 33, 10, 13, 10, 48};
int m = a.length;
System.out.println("Index of a local minima is " + localMin(a, m));
}
}Output:
Index of local minima is 1
Time Complexity: O(Log n)
Auxiliary Space: O (log n), The implicit stack is used since the recursive call is present.