#python #arrays #algorithm #binary-search #index-error
Вопрос:
Программа выдает IndexError: list index out of range двоичный поиск в бесконечном отсортированном массиве, когда элемент не существует или слишком велик
def binarySearch(l,ele,low=0,high=None): if(high==None): high=len(l)-1 if(lowgt;high): return -1 mid= int((low high)/2) pEle = l[mid] if(pEle==ele): return mid elif(pElegt;ele): return binarySearch(l,ele,low,mid-1) else: return binarySearch(l,ele,mid 1,high) # This is a function that searches elements in an infinite sorted array # l=array;ele=element def binarySearchInfiniteSortedArray(l,ele): low,high=0,1 while(True): pEle = l[high] if(pEle==ele): return high elif(pElegt;ele or pEle==l[-1]): break else: low,high = high 1,high*2 return binarySearch(l,ele,low,high) Комментарии:
1. Вы можете попробовать использовать среднее арифметическое, чтобы попасть в диапазон, однако среднее геометрическое приведет вас к ответу быстрее.
Ответ №1:
значение of high удваивается в каждом цикле, и когда значение high становится больше или равно длине списка, он дает IndexError: list index out of range
def binarySearchInfiniteSortedArray(l,ele): low,high=0,1 while(True): try: pEle = l[high] except: high = int((high**0.5)*(low**0.5)) continue if(pEle==ele): return high elif(pElegt;ele or pEle==l[-1]): break else: low,high = high 1,high*2 return binarySearch(l,ele,low,high) Как только ошибка обнаружена, мы можем попробовать, кроме как получить среднее геометрическое значение high и low , если только вы снова не окажетесь в пределах диапазона или не получите ответ. Надеюсь, мои соображения ясны.