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

Question

Я пытаюсь реализовать бинарный поиск в 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"

Answer 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 остановится, как только вы достигнете меньшего числа (с левой стороны)номер (с правой стороны)

Пример:

>>> 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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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)

Answer 7

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

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

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

Answer 8

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

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)

Answer 9

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

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)

Answer 10

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

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:])