Если вы делаете это в .Net и правильно ссылаетесь на файл сценария, и вы отлично выглядите jQuery, убедитесь, что ваши пользователи имеют доступ к файлу сценария. Проект, над которым я работал (коллега), имел свой web.config, запрещающий доступ к анонимным пользователям. Страница, над которой я работал, была доступна анонимным пользователям, поэтому у них не было доступа к файлу скрипта. Выложил следующее в web.config, и все было в мире:
<location path="Scripts">
<system.web>
<authorization>
<allow users="*"/>
</authorization>
</system.web>
</location>
В случае, когда needle_element > array[mid]
, вы в настоящий момент передаете array[mid:]
на рекурсивный вызов. Но вы знаете, что array[mid]
слишком мал, поэтому вы можете передать array[mid+1:]
вместо этого (и соответственно отрегулировать возвращаемый индекс).
Если игла больше всех элементов массива, этот путь в конечном итоге даст вам пустой массив, и ошибка будет повышена, как ожидалось.
Примечание. Создание подматрицы каждый раз приведет к плохой производительности для больших массивов. Лучше пройти в границах массива.
Вы можете улучшить свой алгоритм, как предлагали другие, но давайте сначала посмотрим, почему он не работает:
Вы застреваете в цикле, потому что, если needle_element > array[mid]
, вы включаете элемент mid
в двухполюсном массиве, который вы ищете в следующем. Поэтому, если игла не находится в массиве, вы в конечном итоге будете искать массив длиной один навсегда. Pass array[mid+1:]
вместо этого (это законно, даже если mid+1
не является допустимым индексом), и вы в конечном итоге вызовете свою функцию с массивом нулевой длины. Таким образом, len(array) == 0
означает «не найден», а не ошибка. Обращайтесь с ним соответствующим образом.
Он возвращает индекс ключа в массиве с помощью рекурсивного.
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)
Было бы гораздо лучше работать с индексами 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
Вы можете просто проверить, что needle_element
находится в границах массива, прежде чем начать вообще. Это сделает его более эффективным, так как вам не придется делать несколько шагов, чтобы добраться до конца.
if needle_element < array[0] or needle_element > array[-1]:
# do something, raise error perhaps?
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
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)
Если вы выполняете двоичный поиск, я предполагаю, что массив отсортирован. Если это правда, вы должны иметь возможность сравнить последний элемент в массиве с needle_element
. Как говорит осьминог, это можно сделать до начала поиска.
Все приведенные выше ответы верны, но я думаю, что это помогло бы поделиться моим кодом
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 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:])
Почему бы не использовать модуль bisect? Он должен выполнить нужную вам работу - меньше кода для вас, чтобы поддерживать и тестировать.
Это хвостовое рекурсивное решение, я думаю, что это чище, чем копирование частичных массивов, а затем отслеживание индексов для возврата:
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)
Использование рекурсии:
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)