Поиск максимального значения в наборе

Question

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

Расстояние между значениями произвольное, а количество значений увеличивающейся стороны может отличаться от количества значений на стороне уменьшения.

Какой был бы лучший способ? Проверьте элемент 1, затем последний элемент, затем половину между? И повторить? Или что-то более сложное?

Каким будет время обработки для такого алгоритма?

Answer 1

Вы можете использовать двоичный поиск, сравнивая два соседних элемента вместо одного элемента с фиксированным значением. Начните с a: = 0, b: = n, i: = (a + b)/2 и сравните элемент (i) с элементом (i + 1). Если вы заметили e (i + 1)> e (i), вы знаете, что точка останова находится где-то после i, поэтому установите a: = i. Если e (i) < e (i-1), выполняется обратное, и вы устанавливаете b: = i.

Сложность тогда будет O (log n). Это будет немного медленнее обычного двоичного поиска, потому что вам нужно больше сравнений.

Answer 2

Вы можете попробовать rcursive algorithm, сравнимый с упорядоченным поиском, в зависимости от количества элементов в вашем списке.

псевдокод:

List search(int index, List listpart){ 
    if(listpart.length()==1){ // already found 
     return listpart 
    } 
    else if(listpart(index+1)>listpart(i) && listpart(index-1)<listpart(i)){ //search right part 
     List listpart_tmp = getlistpart(listpart, index, listpart.length()) 
     return search(index+(listpart.length()/4), listpart_tmp 
    } 
    else if(listpart(index+1)<listpart(i) && listpart(index-1)>listpart(i)){ //search left part 
     List listpart_tmp = getlistpart(listpart, 0, index) 
     return search(index-(listpart.length()/4), listpart_tmp 
    } 
    else if(listpart(index+1)<listpart(i) && listpart(index-1)<listpart(i)){ //found 
     return getlistpart(listpart, index, index) 
    } 
} 

Функция

getlistpart 

это функция, которая возвращает список, состоящий из элементов в исходном списке между данными показателями.