Бинарный поиск

Бинарный поиск

21 ноября 2015 г. 22:03

2242 просмотров

0 лайков

0 в избранном

Бинарный поиск:



# -*- coding: UTF-8 -*-
import profile
import random

#простая версия бинарного поиска
def binarySearch1(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    return found

#рекурсивная версия версия поиска
def binarySearch2(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch2(alist[:midpoint],item)
            else:
                return binarySearch2(alist[midpoint+1:],item)


testlist = [x for x in xrange(100000000)]
profile.run('arr=binarySearch1(testlist, 2)') #9.218 seconds
profile.run('arr=binarySearch2(testlist, 2)') #6.883 seconds (25 рекурсивных вызова)

Комментарии 0

Поиск

Рубрики

Популярные теги

Недавние статьи