Блог

Я хотел бы выполнить двоичный поиск элемента в массиве интервалов. Например, мне нужно найти индекс интервала, который включает 35 дюймов intervals = [[1,10], [11, 18], [21, 24], [25, 32], [33, 40], [42, 43]] . Кроме того, если число не найдено ни в одном из интервалов, алгоритм должен вернуть -1. Возможно ли это на python3? Как я могу изменить свою стандартную двоичную функцию поиска, чтобы она возвращала то, что мне нужно? Вот как выглядит моя двоичная функция поиска:

 def b_search(array, element, start, end):
    if start > end:
        return -1
    mid = (start   end) // 2
    if element == array[mid]:
        return mid
    if element < array[mid]:
        return b_search(array, element, start, mid-1)
    else:
        return b_search(array, element, mid 1, end)
  

Заранее спасибо.

 intervals = [[1,10], [11, 18], [21, 24], [25, 32], [33, 40], [42, 43]]
number = 50
idx_list = [i for i,interval in enumerate(intervals) if interval[0] <= number <= interval[1]]
idx = -1  if not idx_list else idx_list[0]
print(idx)
  

Для двоичного поиска используйте приведенный ниже код:

 def b_search_2d(arr_2d, element, start=0, end=0):
    if end == 0:
        end = len(arr_2d) - 1
    if start > end:
        return -1
    mid = (start   end) // 2
    if arr_2d[mid][0] <= element <= arr_2d[mid][1]:
        return mid
    elif element < arr_2d[mid][0]:
        return b_search_2d(arr_2d, element, start, mid-1)
    else:
        return b_search_2d(arr_2d, element, mid 1, end)       
intervals = [[1,10], [11, 18], [21, 24], [25, 32], [33, 40], [42, 43]]
print(b_search_2d(intervals, 35))
print(b_search_2d(intervals, 50))
  

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

 def b_search(array, element, start, end):
    if start > end:
        return -1
    mid = (start   end) // 2
    if array[mid][0] <= element <= array[mid][1]:
        return mid
    if element < array[mid][0]:
        return b_search(array, element, start, mid-1)
    return b_search(array, element, mid 1, end)