бинарный поиск python3 не работает [дубликат]

Если вы делаете это в .Net и правильно ссылаетесь на файл сценария, и вы отлично выглядите jQuery, убедитесь, что ваши пользователи имеют доступ к файлу сценария. Проект, над которым я работал (коллега), имел свой web.config, запрещающий доступ к анонимным пользователям. Страница, над которой я работал, была доступна анонимным пользователям, поэтому у них не было доступа к файлу скрипта. Выложил следующее в web.config, и все было в мире:

  <location path="Scripts">
    <system.web>
      <authorization>
        <allow users="*"/>
      </authorization>
    </system.web>
  </location>
11
задан AbdulFattah Popoola 29 February 2012 в 16:55
поделиться

13 ответов

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

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

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

8
ответ дан interjay 26 August 2018 в 08:29
поделиться

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

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

2
ответ дан alexis 26 August 2018 в 08:29
поделиться

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

round () - это функция, конвертирующая float в integer и быстро создающая код и идущая в ожидаемый регистр [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)
0
ответ дан Anıl Selvi 26 August 2018 в 08:29
поделиться

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

Пример:

>>> 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
12
ответ дан Cartesian Theater 26 August 2018 в 08:29
поделиться

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

if needle_element < array[0] or needle_element > array[-1]:
    # do something, raise error perhaps?
0
ответ дан Donald Miner 26 August 2018 в 08:29
поделиться

array [mid:] создает новую под-копию каждый раз, когда вы вызываете ее = медленно. Также вы используете рекурсию, которая в 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
6
ответ дан Ecir Hana 26 August 2018 в 08:29
поделиться
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)
0
ответ дан Kir Chou 26 August 2018 в 08:29
поделиться

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

0
ответ дан macduff 26 August 2018 в 08:29
поделиться

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

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)
0
ответ дан Maysara 26 August 2018 в 08:29
поделиться

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

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:])
0
ответ дан nettrino 26 August 2018 в 08:29
поделиться

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

4
ответ дан Pierce 26 August 2018 в 08:29
поделиться

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

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)
-1
ответ дан Sean 26 August 2018 в 08:29
поделиться

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

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)
0
ответ дан Stephen Rauch 26 August 2018 в 08:29
поделиться
Другие вопросы по тегам:

Похожие вопросы: