Рубрики

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

Мы в основном игнорируем половину элементов сразу после одного сравнения.

  1. Сравните х со средним элементом.
  2. Если x соответствует среднему элементу, мы возвращаем средний индекс.
  3. Иначе Если x больше среднего элемента, то x может находиться только в правой половине подрешетки после среднего элемента. Таким образом, мы вернемся к правой половине.
  4. Остальное (х меньше) повторяется для левой половины.


Рекурсивный:

# Программа 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"

Выход:

Element is present at index 3

Повторяющийся:

# Итеративная функция двоичного поиска
# Возвращает местоположение 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"

Выход:

Element is present at index 3

Пожалуйста, обратитесь к полной статье о бинарном поиске для более подробной информации!

Рекомендуемые посты:

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

0.00 (0%) 0 votes