CareerCup

My solution is between O(n) and O(logn). Check my website for detail: allenlipeng47.com/PersonalPage/index/view/128/nkey

1. Every time, check the middle element. If middle element is both smaller than left and right element, return middle.
2. Or if left of middle element is both smaller than left and middle element, there must be a local min in left part. Go left part.
3. Or if right of middle element is both smaller than right and middle element, there must be a local min in right part. Go right part.
4. Despite the above 3 cases, we should both check left and right part.

package feb;

public class LocalMin {

	public static void main(String[] args) {
		int[] arr = { 11, 5, 12, 7, 4, 0, 6 };
		int result = localMin(arr);
		System.out.println(result);
	}

	public static int localMin(int[] arr) {
		return localMinUtil(arr, 0, arr.length - 1);
	}

	/*
	 * Return local minimum in arr[left,...,right]
	 */
	private static int localMinUtil(int[] arr, int left, int right) {
		if (right - left < 2) {
			return -1;
		}
		int mid = (left + right) >> 1;
		if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
			return mid;
		}
		if (arr[mid - 1] < arr[mid] && arr[mid - 1] < arr[left]) {
			// There must be localMin in arr[left,...,mid]
			return localMinUtil(arr, left, mid);
		}
		if (arr[mid + 1] < arr[mid] && arr[mid + 1] < arr[right]) {
			// There must be localMin in arr[mid,...,right]
			return localMinUtil(arr, mid, right);
		}
		int result = localMinUtil(arr, left, mid);
		if (result != -1) {
			return result;
		}
		return localMinUtil(arr, mid, right);
	}

}

Binary search will not work since the array is not sorted. Going to the right half of the array for example might not yield a Local Minimum, whilst one may exist in the left half, which is totally missed. Try this array out: 6 2 4 2 8 6 4 1 9 5 4 3 2 2

If there are multiple "local minimum", what should I do? Return all of them, or just one of them is enough?

The trivial solution requires the complexity O(n), is it correct? What do you mean by "trivial solution"

Hint: Use binary search.

Hello

The trivial one requires O(2n). If I gives a solution of O(n), is it OK?

Or I really need to provide a solution such as O(log(n))?

Here is my solution. Time complexity O(logn).

public class FIndLocalMinimum{
	public int localMinimum(int [] arr, int left, int right){
		if(left == right) return left;
		if(right - left == 1) {
			if(arr[left] < arr[right])
				return left;
			else
				return right;
		}
		int mid = left + (right - left) / 2;
		int result = -1;
		if(arr[mid - 1] > arr[mid] && arr[mid + 1] > arr[mid])
			result = mid;
		else{
			if(arr[mid - 1] < arr[mid])
				result = localMinimum(arr, left, mid - 1);
			else if(arr[mid + 1] < arr[mid])
				result = localMinimum(arr, mid + 1, right);
		}
		return result;
	}
	public static void main(String [] args){
		FIndLocalMinimum c = new FIndLocalMinimum();
		int [] test = new int[7];
		test[0] = 11;
		test[1] = 5;
		test[2] = 12;
		test[3] = 7;
		test[4] = 4;
		test[5] = 0;
		test[6] = 6;
		System.out.println(c.localMinimum(test, 0, test.length - 1));
	}
}

Binary search O(logn)

public static int findLocalMin(int[] arr){
	return (arr.length == 0) ?
                Integer.MIN_VALUE
                :findLocalMin(arr, 0, arr.length-1);
    }

    private static int findLocalMin(int[] arr, int l , int r){
        int m = l + (r-l)/2;
        if (m == 0 || m == arr.length - 1){
            return arr[m];
        }
        if (arr[m-1] > arr[m] && arr[m] < arr[m+1]){
            return arr[m];
        }
        else if (arr[m] > arr[m+1]){
            return findLocalMin(arr, m+1, r);
        }
        else{
            return findLocalMin(arr , l , m-1);
        }
    }

Another solution is we use index i to iterate arr from beginning to end. Difference is that we should try to compare arr[i] and arr[i+1]. If arr[i]<arr[i+1], then i should jump 2 to forward.
In this way, iteration could be done faster.

This is my solution:

import java.io.*;

public class FindLocalMinimum{
  public static void main(String args[]){
    // int [] array = {11, 5, 12, 7, 4, 0, 6};
    // int [] array =  { 1, 3, 2, 4, 5, 7, 8, 9 };
    int [] array = {6 ,2 ,4 ,2 ,8 ,6 ,4 ,1 ,9, 5, 4, 3, 2, 2};

    System.out.println(findLocalMin(array, 0, array.length-1));
  }

  public static int findLocalMin(int[] array, int l, int r){
    System.out.println("findLocalMin" + l + " " + r);
    if(l > r){
      return -1;
    }

    if(l == r){
      if(l == 0 && l+1 < array.length){
        return (array[l] < array[l+1] ? l : -1);
      } else if(l == array.length-1){
        return (array[l] < array[l-1] ? l : -1);
      } else{
        return (array[l] < array[l-1] && array[l] < array[l+1])? l : -1;
      }
    }

    int mid = l + (r-l)/2;
    System.out.println("mid:" + mid + " " + array[mid]);

    if(mid == 0){
      return array[mid] < array[mid+1] ? mid : -1;
    } else if(mid == array.length-1){
      return array[mid] < array[mid-1] ? mid: -1;
    } else{
      if(array[mid] < array[mid-1] && array[mid] < array[mid+1]){
        return mid;
      } else{
        int leftIndex = findLocalMin(array, l, mid-1);

        if(leftIndex == -1){
          return findLocalMin(array, mid+1, r);
        } else{
          return leftIndex;
        }
      }
    }
  }
}

// Local minimum

// On high level binary search is used:
// 1) escape long streak of monotone values,
// 2) degenerates to gradient-descent on ranges with 2 or 3 elements

#include <iostream>

//int L = 8;
//int arr[] = { 1, 3, 2, 4, 5, 7, 8, 9 };
//int L = 7;
//int arr[] = { 30, 10, 20, 25, 14, 12, 8 };
int L = 3;
int arr[] = { 3, 2, 1 };

int indexMinimum(int a[], int al) {
  int lb = 0;
  int ub = al-1;
  while (lb < ub) {
    int mid = lb + (ub - lb + 1)/2;
    if (a[lb] < a[mid]) {
      ub = mid-1;
    }
    else {
      lb = mid;
    }
  }
  return lb;
}

int main() {
  int index = indexMinimum(arr, L);
  std::cout << "arr[" << index << "] = " << arr[index] << std::endl;
}

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
        int arr[10]={24,2,23,4,45,1,34,45,46,56};
        int i;
        for(i=1;i<=10;i=i+2)
        {
                if(arr[i]<arr[i-1]&&arr[i]<arr[i+1])
                        printf("\t%d",arr[i]);
        }
        printf("\n");
        return 0;
}

Define two consecutive elements a[i], a[i+1] of the array to be a "falling edge" if a[i] > a[i+1] and a "rising edge" if a[i] < a[i+1]. The idea behind successfully applying binary search is that a local minimum is located inbetween a falling and a rising edge.

A rising edge at the beginning of the array is already a local minimum by definition. The same goes for a falling edge at the end of the array.

So for the general case, we can assume that the part of the array our binary search is looking at has a falling edge at its left (lower) and a rising edge at its right (upper) end. Now inspect two elements near the middle and check whether they are a falling or a rising edge. If falling, a local minimum must be located to the right of the middle. If rising, then to the left of the middle.

def lmin (a):
        if a[0] < a[1]:
                return 0
        if a[-1] < a[-2]:
                return len (a) - 1

        # l points to a falling edge
        # r points to a rising edge
        l = 0
        r = len (a) - 1

        while r - l != 2:
                m = (l + r) // 2
                if a[m] < a[m + 1]:
                        r = m + 1
                else:
                        l = m

        return l + 1

public class LocalMinimumGoogle {

// only needs to find the first local minimum and not all the local minimums present
public static void findLocalMin(int[] a, int low, int high) {

int mid = low + (high - low) / 2;
if (a[mid]!=a[0] && a[mid]!=a[a.length-1]) {
if (a[mid] < a[mid + 1] && a[mid] < a[mid - 1]) {
System.out.println("First Local minimum found is: " + a[mid] + " at position: " + mid);
} else if (a[mid - 1] < a[mid]) {
findLocalMin(a, low, mid);
} else {
findLocalMin(a, mid + 1, high);
}
} else {
if (a[low] < a[low+1]) {
System.out.println("Local minimum is the first element: " + a[low]);
} else if (a[high] < a[high-1]) {
System.out.println("Local mimimum is the last element of the array: " + a[high]);
} else {
System.out.println("no local minimums were found in the inputted array");
}
}

}