Алгоритм двоичного поиска - Python

Question

В python, реализуя алгоритм бинарного поиска, какая математическая функция оптимальна для определения среднего значения - пола или потолка?

Answer 1

Для реализации двоичного поиска в python вам не нужно использовать функцию ceil или floor. В зависимости от проблемы, вы должны округлить среднее значение вверх или вниз.

mid = low + (high-low)/2 #rounds down the mid value 
mid = low + (high-low+1)/2 #rounds up the mid value 

Попытайтесь решить эти две проблемы, вы получите представление о том, как это работает.

1. Дан массив А и целевое значение, возвращает индекс первого элемента в А равно или больше, чем целевое значение
2. Учитывая массив А и целевое значение, возвращают индекс последнего элемента который меньше целевого значения.

Сначала попробуйте эти проблемы самостоятельно, и если вы застряли, обратитесь к this.

Answer 2

Из того, что я понимаю о floor и ceil, не представляется более оптимальным вариантом. Вы можете найти more на этом сайте.

Answer 3

Вы на самом деле не нужно использовать CEIL или пол @shivam_mitra упоминается. При необходимости это алгоритм двоичного поиска.

def bSearch(L, e, low, high): 
    """ 
    L: is a sorted list 
    e: is the targeted number 
    low: is the lowest value of the list 
    hight: is the highest value of list 
    """ 
    if len(L) == 0:     # empty list 
     return False 

    if high == low:     # if the list is one element 
     return L[low] == e 

    mid = low + int((high - low)/2) 

    if L[mid] == e:     # If the midpoint is the targeted number 
     return True 
    if L[mid] > e:      # check if the number is in the lower half of the list 
     return bSearch(L, e, low, mid - 1) 
    else:        # otherwire it is in the higher of the list 
     return bSearch(L, e, mid + 1, high)