CODEWITHSUNDEEP
javaalgorithmdata-structures
Nohsib
Nohsib

Reputation: 3712

algorithm to find max and min in a increasing,decreasing, increasing and decreasing array

Given an array , in which either the values are only increasing or only decreasing or increasing and then decreasing, How to find the max and min value of such and array?

min value is nothing but the smallest of the end values.

but how to find max value?

One way is the linear approach with running time of O(n), can this be solved in O(logn), using some modification to the binary search?

Any code (in java) is highly appreciated.

Thanks
Nohsib

Upvotes: 1

Views: 2837

Answers (5)

Nohsib
Nohsib

Reputation: 3712

According to the logic suggested by Jean-Bernard Pellerin

(only max value is found in this code)

public class max_in_increasing_decreasing_array 
{
    public static int max (int a,int b,int c)
    {

    int maxi=-1;

    if(a>maxi)
        maxi=a;
    if(b>maxi)
        maxi=b;
    if(c>maxi)
        maxi=c;


    return maxi;
}
public static void chkmax(int a[],int low,int high)
{
    int mid=(low+high)/2;
    if(low==high)
    {
        System.out.println(a[low]);
        return;
    }
    if(low+1==high)
    {
        System.out.println(max(a[low],a[high],-1));
        return;
    }

    if((a[mid-1]< a[mid]) && (a[mid] < a[mid+1]))
    {
        chkmax(a, mid+1, high);

    }
    else if((a[mid-1]> a[mid]) && (a[mid] > a[mid+1]))
    {
        chkmax(a, low, mid-1);

    }
    else
        System.out.println(max(a[mid-1],a[mid],a[mid+1]));
}

public static void main(String[] args) 
{
    int a[]={6,7,4,3,2,1};
    chkmax(a, 0,a.length-1);
}

}

Upvotes: 0

Richard Povinelli
Richard Povinelli

Reputation: 1439

An order-statistic tree will do what you want. It can find any order statistic, including min and max, in O(lgn). Forming the tree costs costs O(nlgn), which is the same complexity as the best comparison sort. Adding or removing elements also costs O(lgn).

Here is a link (OrderStatisticTree.java) to a java implementation of an order-statistic tree.

However, given the assumptions you've stated, the min can be found in O(1) as you've indicated. The max can be found in O(lgn). Here is the pseduo code:

findMax(array,n,m)
  middle = (n + m) / 2;

  //check for short array (length 1 or 2) to avoid indexing errors
  if middle == n && array(middle) > array(m)
    return(array(middle));
  else
    return(array(m));

  if array(middle) > array(middle - 1) //left side of peak
    if array(middle) < array(middle + 1) //at peak
      return(array(middle));
    else
      return(findMax(array(middle,m)); //peak is to the right
  else //right side of peak
    return(findMax(array,n,middle); //peak is to the left

Upvotes: 0

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

if [1] < [2]
  if [end-1] < [end]
    min = [1]
    max = [end]
  else
    min = min([1],[end])
    max = binarysearch()
else
  min = [end]
  max = [1]

binarysearch:
take the middle element [mid]
if [mid-1] < [mid] < [mid+1]
  binary search [mid - end]
else if [mid-1] > [mid] > [mid+1]
  binary search [start - mid]
else
  return max([mid-1],[mid],[mid+1]

Upvotes: 3

Adithya Surampudi
Adithya Surampudi

Reputation: 4454

by binary search, see which case it belongs to. Essentialy try to find the first pivot point where there is bigger element immediately followed by smaller say p1, and first pivot point where there is a smaller element immediately followed by bigger element say p2. You can do these both with binary search (google for binary search in a rotated sorted array)

if p1 exists p2 doesnt, its an increasing sequence (min = a[0] max=a[n])

if p2 exists and p1 doesnt, its a decreasing sequence(min = a[n] max=a[0])

if both exists, its increasing and decreasing

min = min(a[0],a[n]) \\first and last
max = a[p1] \\first point where bigger element is followed by a smaller one

Upvotes: 2

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

In cases where the slope goes from increasing to decreasing at most once, the maximum occurs when the derivative first goes negative. In other words, x[i] is the maximum for the smallest value of i that satisfies (x[i+1] - x[i]) < 0.

You can indeed find this with a binary search in O(log n) time. At every iteration, check whether the derivative is negative. If it is, then move left, otherwise move right.

Upvotes: 6

Related Questions