Найти высоту горы

21 Август 2019 - Время чтения: 16 минуты

Условие задачи: Дан массив, в котором числа сначала возрастают, а потом убывают. Найти максимальный элемент в таком массиве эффективным способом. Известно, что в массиве не менее трёх элементов.

Решение: Если элемент меньше следующего, значит он находится на левом (возрастающем) склоне горы. Если следующий меньше текущего - он на правом (убывающем) склоне. Очевидно, мы можем применить бинарный поиск.

Для этого будем рассматривать не элементы, а промежутки между ними. Их всегда на единицу меньше, чем самих элементов. Если промежуток характеризуется тем, что элемент слева от него меньше правого, то отбросим этот промежуток и все левее него. Если больше, то это, возможно, и есть нужный нам промежуток. На каждом шаге будем уменьшать длину рассматриваемого подмассива вдвое. Таким образом, мы рано или поздно найдём искомый промежуток.

Допустим, у нас есть массив:
[1, 2, 3, 5, 4, 0]

Представим его в таком виде:
1 < 2 < 3 < 5 > 4 > 0

Можно объяснить работу алгоритма и так: если представить, что "<" меньше, чем ">" (например, заменить их на 0 и 1 соответственно), то мы получим неубывающий массив, а в таком массиве напрашивается применение бинарного поиска.

(1) 0 (2) 0 (3) 0 (5) 1 (4) 1 (0)

В скобках - элементы, но мы рассматриваем промежутки между ними. Они образуют последовательность, в которой за группой нулей идёт группа единиц. Найти самую левую из них - это то же самое, что найти первый максимум.


Исходный код на C#
using System;
using System.Linq;
 
class Program
{
    public static void Main()
    {
        int[] arr = Console.ReadLine().Split().Select(Int32.Parse).ToArray();
        int begin = 0;
        for (int lim = arr.Length - 1; lim > 0; lim /= 2)
        {
            int p = begin + lim / 2;
            if (arr[p] < arr[p + 1])
            {
                begin = p + 1;
                --lim;
            }
        }
        Console.WriteLine($"arr[{begin}] = {arr[begin]}");
    }
}

Исходный код на Python
arr = [int(i) for i in input().split()]
base = 0
lim = len(arr) - 1
while lim > 0:
    p = base + lim // 2
    if arr[p] < arr[p + 1]:
        base = p + 1
        lim -= 1
    lim //= 2
print("arr[{}] = {}".format(base, arr[base]))

Исходный код на C99
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    int *arr = NULL;
    size_t siz = 0;
    for (int x; scanf("%d", &x) == 1;) {
        arr = realloc(arr, sizeof(int) * ++siz);
        arr[siz - 1] = x;
    }
    size_t base = 0;
    for (--siz; siz != 0; siz >>= 1) {
        size_t p = base + (siz >> 1);
        if (arr[p] < arr[p + 1]) {
            base = p + 1;
            --siz;
        }
    }
    printf("arr[%u] = %d\n", (unsigned)base, arr[base]);
    free(arr);
    return 0;
}

Интересно, что тот же самый алгоритм будет прекрасно работать и для другой, хотя и очень похожей задачи: найти любой локальный максимум в массиве, т.е. такой элемент, который больше обоих своих непосредственных соседей.

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории