Программа Python для бинарного поиска (рекурсивная и итеративная)

# Программа Python для рекурсивного бинарного поиска.

  
# Возвращает индекс x в arr, если присутствует, иначе -1

def binarySearch (arr, l, r, x):

    # Проверьте базовый случай

    if r >= l:

        mid = l + (r - l)/2

        # Если элемент присутствует в самой середине

        if arr[mid] == x:

            return mid

        # Если элемент меньше середины, то он может только

        # присутствовать в левом подмассиве

        elif arr[mid] > x:

            return binarySearch(arr, l, mid-1, x)

        # В противном случае элемент может присутствовать только в правом подмассиве

        else:

            return binarySearch(arr, mid+1, r, x)

    else:

        # Элемент отсутствует в массиве

        return -1

  
# Тестовый массив

arr = [ 2, 3, 4, 10, 40 ]

x = 10

  
# Вызов функции

result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:

    print "Element is present at index %d" % result

else:

    print "Element is not present in array"

# Итеративная функция двоичного поиска
# Возвращает местоположение x в указанном массиве arr, если присутствует,
# еще возвращает -1

def binarySearch(arr, l, r, x):

    while l <= r:

        mid = l + (r - l)/2;

        # Проверьте, присутствует ли х в середине

        if arr[mid] == x:

            return mid

        # Если х больше, игнорировать левую половину

        elif arr[mid] < x:

            l = mid + 1

        # Если х меньше, игнорируйте правую половину

        else:

            r = mid - 1

    # Если до нас дойдут, то элемента нет

    return -1

  
# Тестовый массив

arr = [ 2, 3, 4, 10, 40 ]

x = 10

  
# Вызов функции

result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:

    print "Element is present at index %d" % result

else:

    print "Element is not present in array"