алгоритм нахождения максимума и минимума в возрастающем, убывающем, растущем и убывающем массиве

Question

Учитывая массив, в котором либо значения только увеличиваются или только уменьшаются или увеличиваются, а затем уменьшаются, Как найти максимальное и минимальное значения таких и массивов?

Мин. Значение - не что иное, как наименьшее из конечных значений.

а как найти максимальное значение?

Одним из способов является линейный подход со временем выполнения O (n). Может ли это быть решено в O (logn) с использованием некоторой модификации двоичного поиска?

Любой код (в Java) высоко ценится.

Спасибо
Nohsib

Answer 1

В случаях, когда наклон изменяется от увеличения к уменьшению не более одного раза, максимум наступает, когда производная сначала становится отрицательной. Другими словами, x[i] является максимумом для наименьшего значения i, которое удовлетворяет (x[i+1] - x[i]) < 0.

Вы действительно можете найти это с помощью двоичного поиска во O(log n) времени. На каждой итерации проверяйте, отрицательна ли производная. Если это так, то двигайтесь влево, в противном случае двигайтесь вправо.

Answer 2

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]

Answer 3

бинарным поиском, посмотрите, к какому случаю он относится. По сути, попробуйте найти первую точку поворота, где сразу за большим элементом следует меньший элемент p1, и первую точку поворота, где сразу за меньшим элементом следует более крупный элемент, например p2. Вы можете сделать это и с двоичным поиском (Google для двоичного поиска в повернутом отсортированном массиве)

если p1 существует, p2 нет, его возрастающая последовательность (min = a [0] max = a [n])

если p2 существует, а p1 нет, то это убывающая последовательность (min = a [n] max = a [0])

если оба существуют, то увеличиваются и уменьшаются

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

Answer 4

Согласно логике, предложенной Жаном-Бернаром Пеллереном

(в этом коде найдено только максимальное значение)

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);
}

}

Answer 5

дерево статистики заказов будет делать то, что вы хотите.Он может найти любую статистику заказа, включая min и max, в O (lg n ).Формирование дерева стоит O ( n lg n ), что является такой же сложностью, что и лучший вариант сравнения.Добавление или удаление элементов также стоит O (lg n ).

Вот ссылка ( OrderStatisticTree.java ) на реализацию java дерева статистики заказов.

Однако, учитывая высказанные вами предположения, мин можно найти в O (1), как вы указали.Максимум можно найти в O (lg n ).Вот псевдо-код:

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