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

Я пытаюсь реализовать бинарный поиск в Python и написал его следующим образом. Тем не менее, я не могу заставить его остановиться, когда needle_element больше, чем самый большой элемент в массиве.

Вы можете помочь? Благодарю.

def binary_search(array, needle_element):
    mid = (len(array)) / 2
    if not len(array):
        raise "Error"
    if needle_element == array[mid]:
        return mid
    elif needle_element > array[mid]:
        return mid + binary_search(array[mid:],needle_element)
    elif needle_element < array[mid]:
        return binary_search(array[:mid],needle_element)
    else:
        raise "Error"
Источник

13 ответов

Решение

В том случае, если needle_element > array[mid]Вы проходите array[mid:] на рекурсивный вызов. Но вы знаете, что array[mid] слишком мал, так что вы можете пройти array[mid+1:] вместо этого (и скорректируйте возвращаемый индекс соответственно).

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

Примечание. Создание подмассива каждый раз приводит к снижению производительности больших массивов. Лучше вместо этого передать границы массива.

Источник

Было бы намного лучше работать с lower а также upper индексы, как Лассе В. Карлсен предлагал в комментарии к вопросу.

Это был бы код:

def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            return x
        elif target > val:
            if lower == x:   # these two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x
  • lower < upper остановится, как только вы достигнете меньшего числа (с левой стороны)
  • if lower == x: break остановится, как только вы достигнете большего числа (с правой стороны)

Пример:

>>> binary_search([1,5,8,10], 5)   # return 1
1
>>> binary_search([1,5,8,10], 0)   # return None
>>> binary_search([1,5,8,10], 15)  # return None
Источник

Почему бы не использовать модуль bisect? Он должен выполнять ту работу, которая вам нужна - меньше кода для поддержки и тестирования.

Источник

array[mid:] создает новую суб-копию каждый раз, когда вы ее называете = slow. Также вы используете рекурсию, которая в Python тоже медленная.

Попробуй это:

def binarysearch(sequence, value):
    lo, hi = 0, len(sequence) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sequence[mid] < value:
            lo = mid + 1
        elif value < sequence[mid]:
            hi = mid - 1
        else:
            return mid
    return None
Источник

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

Вы застряли в петле, потому что если needle_element > array[mid]включаешь элемент mid в массиве пополам вы ищете следующий. Так что если игла не находится в массиве, вы в конечном итоге будете искать массив длины один навсегда. Проходить array[mid+1:] вместо этого (это законно, даже если mid+1 не является допустимым индексом), и вы в конечном итоге вызовете свою функцию с массивом нулевой длины. Так len(array) == 0 означает "не найден", не ошибка. Обращайтесь с этим соответствующим образом.

Источник

Все ответы выше верны, но я думаю, что это поможет поделиться моим кодом

def binary_search(number):
numbers_list = range(20, 100)
i = 0
j = len(numbers_list)
while i < j:
    middle = int((i + j) / 2)
    if number > numbers_list[middle]:
        i = middle + 1
    else:
        j = middle
return 'the index is '+str(i)
Источник 
def binary_search(array, target):
    low = 0
    mid = len(array) / 2
    upper = len(array)

    if len(array) == 1:
        if array[0] == target:
            print target
            return array[0]
        else:
            return False
    if target == array[mid]:
        print array[mid]
        return mid
    else:
        if mid > low:
            arrayl = array[0:mid]
            binary_search(arrayl, target)

        if upper > mid:
            arrayu = array[mid:len(array)]
            binary_search(arrayu, target)

if __name__ == "__main__":
    a = [3,2,9,8,4,1,9,6,5,9,7]
    binary_search(a,9)
Источник

Использование рекурсии:

def binarySearch(arr,item):
    c = len(arr)//2
    if item > arr[c]:
       ans = binarySearch(arr[c+1:],item)
       if ans:
          return binarySearch(arr[c+1],item)+c+1
    elif item < arr[c]:
       return binarySearch(arr[:c],item)
    else:
       return c

binarySearch([1,5,8,10,20,50,60],10)
Источник

Это хвостовое рекурсивное решение, я думаю, что оно чище, чем копирование частичных массивов, а затем отслеживание индексов для возврата:

def binarySearch(elem, arr):
    # return the index at which elem lies, or return false
    # if elem is not found
    # pre: array must be sorted
    return binarySearchHelper(elem, arr, 0, len(arr) - 1)

def binarySearchHelper(elem, arr, start, end):
    if start > end:
        return False
    mid = (start + end)//2
    if arr[mid] == elem:
        return mid
    elif arr[mid] > elem:
        # recurse to the left of mid
        return binarySearchHelper(elem, arr, start, mid - 1)
    else:
        # recurse to the right of mid
        return binarySearchHelper(elem, arr, mid + 1, end)
Источник

Если вы делаете бинарный поиск, я предполагаю, что массив отсортирован. Если это правда, вы должны быть в состоянии сравнить последний элемент в массиве с needle_element, Как говорит осьминог, это можно сделать до начала поиска.

Источник

Возвращает логическое значение, если значение находится в списке.

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

def binarySearch(array, value):
  array = sorted(array)
  first = 0
  last = len(array) - 1

  while first <= last:
    midIndex = (first + last) // 2
    midValue = array[midIndex]

    if value == midValue:
      return True
    if value < midValue:
      last = midIndex - 1
    if value > midValue:
      first = midIndex + 1
  return False
Источник

Без нижнего / верхнего индексов это также должно делать:

def exists_element(element, array):
    if not array:
        yield False

    mid = len(array) // 2
    if element == array[mid]:
        yield True
    elif element < array[mid]:
        yield from exists_element(element, array[:mid])
    else:
        yield from exists_element(element, array[mid + 1:])
Источник

Вы можете просто проверить, чтобы увидеть, что needle_element находится в границах массива, прежде чем начать вообще. Это также сделает его более эффективным, так как вам не придется делать несколько шагов, чтобы добраться до конца.

if needle_element < array[0] or needle_element > array[-1]:
    # do something, raise error perhaps?
Источник

Возвращает индекс ключа в массиве с помощью рекурсии.

round () - это функция, конвертирующая число с плавающей точкой в ​​целое число, ускоряющая выполнение кода и переходящая в ожидаемый случай [O(logn)].

A=[1,2,3,4,5,6,7,8,9,10]
low = 0
hi = len(A)
v=3
def BS(A,low,hi,v):
    mid = round((hi+low)/2.0)
    if v == mid:
        print ("You have found dude!" + " " + "Index of v is ", A.index(v))
    elif v < mid:
        print ("Item is smaller than mid")
        hi = mid-1
        BS(A,low,hi,v)
    else :
        print ("Item is greater than mid")
        low = mid + 1
        BS(A,low,hi,v)
BS(A,low,hi,v)
Источник
Другие вопросы по тегам