Блог

Можно ли написать реализацию двоичного поиска следующим образом?

     def binarySearching(sortedArr,v):
    if len(sortedArr)>=1:
        mid = len(sortedArr)//2
        if v<sortedArr[mid]:
            return binarySearching(sortedArr[:mid],v)
        elif v>sortedArr[mid]:
            return binarySearching(sortedArr[mid 1:],v)
        else:
            return mid
        return None
  

Я не понимаю, почему нам нужно указывать low и high для алгоритма.

редактировать: Благодаря @Stef, эта реализация неверна, потому что mid относится не к исходному массиву, а к подмассиву

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

Вы указываете low и high при передаче одного и того же массива для поиска и изменяете только область поиска.

Альтернативой передаче low и high является передача части массива, но в python это означает, что каждый раз, когда вы разрезаете массив (список), вы создаете другой объект (который является нарезанным списком), а это неэффективно расходует память.

Вы должны указать low and high , когда вы работаете с единственным массивом / списком. На каждой итерации вы обрабатываете часть списка в low..high диапазоне.

Ваша реализация создает подсписки, поэтому ей не требуется явное определение диапазона (но является ли это формирование подсписка бесплатным?)

Сравните эти две реализации binarySearch . Первый — ваш, второй — мой.

В вашей версии вы передаете «фрагменты», то есть целые копии подмассивов, рекурсивному вызову. В моей версии все рекурсивные вызовы обращаются к одному и тому же массиву без его копирования, а вместо этого в качестве параметров передаются только low и high .

 # using slices, ie, copies of subarrays
def binarySearching(sortedArr,v):
    # print(sortedArr)
    if len(sortedArr)>=1:
        mid = len(sortedArr)//2
        if v<sortedArr[mid]:
            return binarySearching(sortedArr[:mid],v)
        elif v>sortedArr[mid]:
            return binarySearching(sortedArr[mid 1:],v)
        else:
            return mid
    else:
        return None

# using low and high indices
def otherBinarySearching(sortedArr, v):
    def auxiliary(low, high, v):
        #print(low, high, sortedArr[low:high])
        if high > low:
            mid = (high   low) // 2
            if v < sortedArr[mid]:
                return auxiliary(low, mid, v)
            elif v > sortedArr[mid]:
                return auxiliary(mid 1, high, v)
            else:
                return mid
        elif high == low:
            return (low if v == sortedArr[low] else None)
    return auxiliary(0, len(sortedArr), v)

# add some tests to make sure implementations are correct
if __name__=='__main__':
    a = [x for x in range(0, 101, 2)]
    b = [x for x in range(1, 100, 2)]
    print('a: ', a)
    print('b: ', b)
    print('binarySearching:      ', all(isinstance(binarySearching(a, x), int) for x in a) and all(binarySearching(a, x) is None for x in b))
    print('otherBinarySearching: ', all(otherBinarySearching(a, x) == x / 2 for x in a) and all(otherBinarySearching(a, x) is None for x in b))
  

Кроме того, ваша версия возвращает неправильные индексы: строка return mid возвращает индекс v в подмассиве, который в данный момент просматривает binarySearching, вместо индекса в исходном массиве.