Find a local minima in an array

A local minimum in an array is a value that is smaller than its neighbors. To find local minima in an array, you can iterate through the array and compare each element to its neighbors. Here's an example of how you can implement this in Java:

int findLocalMinima(int[] arr) {
    for (int i = 1; i < arr.length - 1; i++) {
        if (arr[i] < arr[i-1] && arr[i] < arr[i+1]) {
            return arr[i];
        }
    }
    return -1; // Not found
}

This implementation has a time complexity of O(n) because it iterates through the array once. Note that this implementation assumes that the input array has at least 3 elements, otherwise it will throw an ArrayIndexOutOfBounds exception.

Alternatively, you can use a binary search approach to find a local minimum in an array. First, check the middle element of the array. If it is smaller than its neighbors, it is a local minimum. If the middle element is greater than its left neighbor, then the local minima must be present in the left sub-array. If the middle element is greater than its right neighbor, then the local minima must be present in the right sub-array. You can then recursively apply the same approach to the left or right sub-array until the local minima are found. Here's an example of how you can implement this in Java:

int findLocalMinima(int[] arr, int left, int right) {
    int mid = left + (right - left) / 2;
    if (mid == 0 || arr[mid - 1] > arr[mid] && (mid == arr.length - 1 || arr[mid + 1] > arr[mid])) {
        return arr[mid];
    }
    else if (arr[mid - 1] < arr[mid]) {
        return findLocalMinima(arr, left, mid - 1);
    }
    else {
        return findLocalMinima(arr, mid + 1, right);
    }
}