найти k-й элемент в унимодальном массиве

Question

Учитывая унимодальный массив A из n отдельных элементов (что означает, что его записи в порядке возрастания вплоть до его максимального элемента, после чего его элементы находятся в порядке убывания), целое число p (это длина возрастающей первой части) и k (k-й минимальный элемент). Дайте алгоритм для вычисления значения k-го минимального элемента, который выполняется в O (log n) времени.

Пример:

A= {1,23,50,30,20,2} 
p= 2 
k=3 

Ответ: 20

Редактировать

Я попытался это:

def ksmallest(arr1, arr2, k): 
if len(arr1) == 0: 
    return arr2[len(arr2)-k-1] 
elif len(arr2) == 0: 
    return arr1[k] 
mida1 = (int)(len(arr1)/2) 
mida2 = (int)((len(arr2)-1)/2) 
if mida1+mida2<k: 
    if arr1[mida1]>arr2[mida2]: 
     return ksmallest(arr1, arr2[:mida2], k-(len(arr2)-mida2)) 
    else: 
     return ksmallest(arr1[mida1+1:], arr2, k-mida1-1) 
else: 
    if arr1[mida1]>arr2[mida2]: 
     return ksmallest(arr1[:mida1], arr2, k) 
    else: 
     return ksmallest(arr1, arr2[mida2+1:], k) 

Answer 1

Для начала еще раз взглянуть на индексах. Вы начинаете с:

if len(arr1) == 0: 
    return arr2[len(arr2)-k-1] 
elif len(arr2) == 0: 
    return arr1[len(arr1)-k-1] 

Но, конечно, если arr1 в порядке возрастания, и arr2 в порядке убывания -й минимальный элемент не будет найден в том же месте.