Бинарные Питона Производительность Поиска


Это моя версия бинарного метода поиска. Что еще я могу сделать, чтобы оптимизировать это?

Я написал комментарии к руководство тех, кто может найти этот код полезным, как он работает. Но я хотел бы обновить его, если это можно сделать быстрее/чище.

def bSearch(arr, val, first, last):

    #Find the index of the middle array value.
    mid = (len(arr)-1)//2

    #If there are no more numbers to search through
    if first >= last:

        #Check if the last number is the number being searched for.
        if (arr[mid] == val):
            print("TRUE")
        else:
            print("FALSE")

    #If there are still numbers to search through
    #check array at index (mid) for the desired value.
    elif (arr[mid] == val):
        print("TRUE")

    elif (arr[mid] < val):
        #nArr = new array = greater half of the original array.
        nArr = arr[len(arr)//2:]
        bSearch(nArr, val, 0, len(nArr)-1)

    elif (arr[mid] > val):
        #nArr = new array = lesser half of the original array.
        nArr = arr[:len(arr)//2]
        bSearch(nArr, val, 0, len(nArr)-1)

#The array used for testing.      
a = [1,2,3,4,6,7,8,10]

print("Test One")
#Search for 5 in array a. Should return false.
bSearch(a, 5, 0, len(a)-1)

print("Test Two")
#Search for 2 in array a. Should return true.
bSearch(a, 2, 0, len(a)-1)

print("Test Three")
#Search for 8 in array a. Should return true.
bSearch(a, 8, 0, len(a)-1)

print("Test Four")
#Search for 1 in array a. Should return true.
bSearch(a, 1, 0, len(a)-1)

print("Test Five")
#Search for 15 in array a. Should return false.
bSearch(a, 15, 0, len(a)-1)


Комментарии
1 ответ

Нерекурсивный подход:

# Binary search in a non-empty sorted array
def bin_search(a, val):
l = 0
r = len(a)
# Trying to find val in a[l:r]
while r - l > 1:
m = (l + r) // 2
if a[m] > val:
r = m
else:
l = m
return a[l] == val

1
ответ дан 1 апреля 2018 в 11:04 Источник Поделиться