Czy istnieje funkcja biblioteki, która wykonuje wyszukiwanie binarne na liście / krotce i zwraca pozycję elementu, jeśli zostanie znaleziona, i „Fałsz” (-1, Brak itd.), Jeśli nie?

Znalazłem funkcje bisect_left / right w module bisect , ale nadal zwracają pozycję, nawet jeśli elementu nie ma na liście. Jest to całkowicie w porządku dla ich zamierzonego zastosowania, ale chcę tylko wiedzieć, czy element znajduje się na liście, czy nie (nie chcę niczego wstawiać).

Pomyślałem o użyciu, bisect_lefta następnie sprawdzeniu, czy pozycja na tej pozycji jest równa temu, czego szukam, ale wydaje się to kłopotliwe (a także muszę sprawdzić, czy liczba może być większa niż największa liczba na mojej liście). Jeśli istnieje ładniejsza metoda, chciałbym się o tym dowiedzieć.

Edytuj Aby wyjaśnić, do czego to jest potrzebne: zdaję sobie sprawę, że słownik bardzo by się do tego nadawał, ale staram się, aby zużycie pamięci było jak najniższe. Moje zamierzone użycie to rodzaj dwukierunkowej tabeli przeglądowej. Mam w tabeli listę wartości i muszę mieć dostęp do wartości na podstawie ich indeksu. Chcę też móc znaleźć indeks określonej wartości lub Brak, jeśli wartość nie znajduje się na liście.

Wykorzystanie do tego słownika byłoby najszybszym sposobem, ale (w przybliżeniu) podwoiłoby wymagania dotyczące pamięci.

Zadałem to pytanie, myśląc, że być może przeoczyłem coś w bibliotekach Pythona. Wygląda na to, że będę musiał napisać własny kod, jak zasugerował Moe.

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to len(a)   
    pos = bisect_left(a, x, lo, hi)  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

Dlaczego nie spojrzeć na kod bisect_left / right i dostosować go do swoich celów.

lubię to:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

To trochę nie na temat (ponieważ odpowiedź Moe wydaje się kompletna na pytanie PO), ale warto przyjrzeć się złożoności całej procedury od początku do końca. Jeśli przechowujesz coś na posortowanych listach (w czym pomogłoby wyszukiwanie binarne), a następnie po prostu sprawdzasz istnienie, ponosisz (najgorszy przypadek, chyba że określono):

Posortowane listy

• O (n log n), aby początkowo utworzyć listę (jeśli są to dane niesortowane. O (n), jeśli są posortowane)
• O (log n) wyszukiwania (to jest część wyszukiwania binarnego)
• O (n) wstaw / usuń (może to być O (1) lub O (log n) przypadek średni, w zależności od wzorca)

Podczas gdy z a set(), ponosisz

• O (n) stworzyć
• Wyszukiwanie O (1)
• O (1) wstaw / usuń

To, co naprawdę daje posortowana lista, to „następny”, „poprzedni” i „zakresy” (w tym wstawianie lub usuwanie zakresów), które są O (1) lub O (| zakres |), biorąc pod uwagę indeks początkowy. Jeśli nie używasz często tego rodzaju operacji, przechowywanie w zestawach i sortowanie w celu wyświetlenia może być ogólnie lepszym rozwiązaniem. set()powoduje bardzo niewielkie dodatkowe obciążenie w Pythonie.

Warto wspomnieć, że dokumenty w połowie zawierają teraz przykłady wyszukiwania: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Podniesienie wartości ValueError zamiast zwracania -1 lub None jest bardziej pythonowe - na przykład list.index () robi to. Ale oczywiście możesz dostosować przykłady do swoich potrzeb.)

Najprościej jest użyć połowy i sprawdzić jedną pozycję wstecz, aby zobaczyć, czy element tam jest:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

To jest prosto z instrukcji:

http://docs.python.org/2/library/bisect.html

8.5.1. Wyszukiwanie posortowanych list

Powyższe funkcje bisect () są przydatne do znajdowania punktów wstawiania, ale mogą być trudne lub niewygodne w użyciu w przypadku typowych zadań wyszukiwania. Poniższych pięć funkcji pokazuje, jak przekształcić je w standardowe wyszukiwania posortowanych list:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Tak więc przy niewielkiej modyfikacji Twój kod powinien wyglądać następująco:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

Zgadzam się, że odpowiedź @ DaveAbrahams przy użyciu modułu z połówką jest poprawnym podejściem. W swojej odpowiedzi nie wspomniał o jednym ważnym szczególe.

Z dokumentów bisect.bisect_left(a, x, lo=0, hi=len(a))

Moduł bisekcji nie wymaga, aby tablica wyszukiwania była obliczana z wyprzedzeniem. Możesz po prostu przedstawić punkty końcowe bisect.bisect_leftzamiast tego, używając wartości domyślnych 0i len(a).

Jeszcze ważniejsze dla mojego zastosowania jest szukanie wartości X takiej, aby zminimalizować błąd danej funkcji. Aby to zrobić, potrzebowałem sposobu, aby algorytm bisect_left wywoływał zamiast tego moje obliczenia. To jest naprawdę proste.

Po prostu podaj obiekt, który definiuje __getitem__jakoa

Na przykład, możemy użyć algorytmu bisect, aby znaleźć pierwiastek kwadratowy z dowolną precyzją!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

Jeśli chcesz tylko sprawdzić, czy jest obecny, spróbuj zmienić listę w dykt:

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

Na moim komputerze polecenie „if n in l” trwało 37 sekund, a „if n in d” 0,4 sekundy.

Ten jest:

• nierekurencyjny (co sprawia, że ​​jest bardziej wydajny w pamięci niż większość podejść rekurencyjnych)
• faktycznie działa
• szybki, ponieważ działa bez żadnych niepotrzebnych jeśli i warunków
• oparty na matematycznym twierdzeniu, że dolna granica (niski + wysoki) / 2 jest zawsze mniejsza niż wysoka, gdzie dolna jest dolną granicą, a wysoka górną granicą.

def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

Rozwiązanie Dave'a Abrahamsa jest dobre. Chociaż zrobiłbym to minimalistycznie:

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

Chociaż w Pythonie nie ma jawnego algorytmu wyszukiwania binarnego, istnieje moduł - bisect- zaprojektowany do znajdowania punktu wstawienia elementu na posortowanej liście przy użyciu wyszukiwania binarnego. Można to „oszukać” w celu wykonania wyszukiwania binarnego. Największą zaletą tego jest ta sama zaleta, jaką ma większość kodu bibliotecznego - jest bardzo wydajny, dobrze przetestowany i po prostu działa (w szczególności wyszukiwania binarne mogą być dość trudne do pomyślnego wdrożenia - szczególnie jeśli przypadki skrajne nie są dokładnie rozważane).

Podstawowe typy

W przypadku podstawowych typów, takich jak Strings lub ints, jest to całkiem proste - wystarczy bisectmoduł i posortowana lista:

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

Możesz również użyć tego, aby znaleźć duplikaty:

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

Oczywiście w razie potrzeby możesz po prostu zwrócić indeks, a nie wartość tego indeksu.

Obiekty

W przypadku niestandardowych typów lub obiektów sprawy są nieco trudniejsze: musisz zaimplementować bogate metody porównywania, aby uzyskać połowę w celu prawidłowego porównania.

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

Powinno to działać przynajmniej w Pythonie 2.7 -> 3.3

Używanie dyktowania nie podwoiłoby zużycia pamięci, chyba że przechowywane obiekty są naprawdę małe, ponieważ wartości są tylko wskaźnikami do rzeczywistych obiektów:

>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True

W tym przykładzie „foo” jest przechowywane tylko raz. Czy to ma dla ciebie znaczenie? A o ilu dokładnie rzeczach mówimy?

Ten kod działa z listami liczb całkowitych w sposób rekurencyjny. Szuka najprostszego scenariusza, który jest następujący: długość listy mniejsza niż 2. Oznacza to, że odpowiedź już istnieje i wykonywany jest test w celu sprawdzenia poprawnej odpowiedzi. Jeśli nie, ustawiana jest wartość środkowa i sprawdzana, czy jest poprawna, jeśli nie bisekcja jest wykonywana przez ponowne wywołanie funkcji, ale ustawienie środkowej wartości jako górnej lub dolnej granicy, przesuwając ją w lewo lub w prawo

def binary_search (intList, intValue, lowValue, highValue):
    if (highValue - lowValue) <2:
        return intList [lowValue] == intValue lub intList [highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue) / 2)
    if intList [middleValue] == intValue:
        powrót True
    if intList [middleValue]> intValue:
        return binary_search (intList, intValue, lowValue, middleValue - 1)
   return binary_search (intList, intValue, middleValue + 1, highValue)

Sprawdź przykłady w Wikipedii http://en.wikipedia.org/wiki/Binary_search_algorithm

def binary_search(a, key, imin=0, imax=None):
    if imax is None:
        # if max amount not set, get the total
        imax = len(a) - 1

    while imin <= imax:
        # calculate the midpoint
        mid = (imin + imax)//2
        midval = a[mid]

        # determine which subarray to search
        if midval < key:
            # change min index to search upper subarray
            imin = mid + 1
        elif midval > key:
            # change max index to search lower subarray
            imax = mid - 1
        else:
            # return index number 
            return mid
    raise ValueError

'''
Only used if set your position as global
'''
position #set global 

def bst(array,taget): # just pass the array and target
        global position
        low = 0
        high = len(array)
    while low <= high:
        mid = (lo+hi)//2
        if a[mid] == target:
            position = mid
            return -1
        elif a[mid] < target: 
            high = mid+1
        else:
            low = mid-1
    return -1

Myślę, że jest to znacznie lepsze i skuteczne. proszę mnie poprawić :) . Dziękuję Ci

• s to lista.
• binary(s, 0, len(s) - 1, find) jest pierwszym wezwaniem.

• Funkcja zwraca indeks poszukiwanego elementu. Jeśli nie ma takiej pozycji, zwraca -1.

  def binary(s,p,q,find):
      if find==s[(p+q)/2]:
          return (p+q)/2
      elif p==q-1 or p==q:
          if find==s[q]:
              return q
          else:
              return -1
      elif find < s[(p+q)/2]:
          return binary(s,p,(p+q)/2,find)
      elif find > s[(p+q)/2]:
          return binary(s,(p+q)/2+1,q,find)

def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid

Wyszukiwanie binarne:

// List - values inside list
// searchItem - Item to search
// size - Size of list
// upperBound - higher index of list
// lowerBound - lower index of list
def binarySearch(list, searchItem, size, upperBound, lowerBound):
        print(list)
        print(upperBound)
        print(lowerBound)
        mid = ((upperBound + lowerBound)) // 2
        print(mid)
        if int(list[int(mid)]) == value:
               return "value exist"
        elif int(list[int(mid)]) < value:
             return searchItem(list, value, size, upperBound, mid + 1)
        elif int(list[int(mid)]) > value:
               return searchItem(list, value, size, mid - 1, lowerBound)

// Aby wywołać powyższą funkcję użyj:

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1        
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))

Potrzebowałem wyszukiwania binarnego w Pythonie i generycznego dla modeli Django. W modelach Django jeden model może mieć klucz obcy do innego modelu i chciałem przeprowadzić wyszukiwanie na obiektach pobranych modeli. Napisałem następującą funkcję, której możesz użyć.

def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
    """
    This is a binary search function which search for given key in values.
    This is very generic since values and key can be of different type.
    If they are of different type then caller must specify `cmp` function to
    perform a comparison between key and values' item.
    :param values:  List of items in which key has to be search
    :param key: search key
    :param lo: start index to begin search
    :param hi: end index where search will be performed
    :param length: length of values
    :param cmp: a comparator function which can be used to compare key and values
    :return: -1 if key is not found else index
    """
    assert type(values[0]) == type(key) or cmp, "can't be compared"
    assert not (hi and length), "`hi`, `length` both can't be specified at the same time"

    lo = lo
    if not lo:
        lo = 0
    if hi:
        hi = hi
    elif length:
        hi = length - 1
    else:
        hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if not cmp:
            if values[mid] == key:
                return mid
            if values[mid] < key:
                lo = mid + 1
            else:
                hi = mid - 1
        else:
            val = cmp(values[mid], key)
            # 0 -> a == b
            # > 0 -> a > b
            # < 0 -> a < b
            if val == 0:
                return mid
            if val < 0:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Wiele dobrych rozwiązań powyżej, ale nie widziałem prostego (KISS, zachowaj prostotę (bo jestem)) głupiego użycia wbudowanej w Pythonie / generycznej funkcji dwusiecznej do wyszukiwania binarnego. Przy odrobinie kodu wokół funkcji połowy, Myślę, że mam poniżej przykład, w którym przetestowałem wszystkie przypadki dla małej tablicy nazw. Niektóre z powyższych rozwiązań nawiązują do tego / mówią, ale mam nadzieję, że poniższy prosty kod pomoże każdemu zdezorientowanemu, tak jak ja.

Python bisect służy do wskazania, gdzie wstawić nową wartość / element wyszukiwania do posortowanej listy. Poniższy kod, który używa bisect_left, który zwróci indeks trafienia, jeśli szukany element na liście / tablicy zostanie znaleziony (Uwaga: bisect i bisect_right zwróci indeks elementu po trafieniu lub dopasuje jako punkt wstawienia) Jeśli nie zostanie znaleziony , bisect_left zwróci indeks do następnego elementu na posortowanej liście, który nie == szukanej wartości. Jedynym innym przypadkiem jest sytuacja, w której element wyszukiwania znalazłby się na końcu listy, gdzie zwracany indeks byłby poza końcem listy / tablicy, a który w kodzie poniżej wczesnego wyjścia przez Pythona z uchwytami logicznymi "i". (pierwszy warunek Fałsz Python nie sprawdza kolejnych warunków)

#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
    search =input("Enter name to search for or 'none' to terminate program:")
    if search == "none":
        break
    i = bisect_left(names,search)
    print(i) # show index returned by Python bisect_left
    if i < (lenNames) and names[i] == search:
        print(names[i],"found") #return True - if function
    else:
        print(search,"not found") #return False – if function
##Exhaustive test cases:
##Enter name to search for or 'none' to terminate program:Zayed
##4
##Zayed found
##Enter name to search for or 'none' to terminate program:Zach
##3
##Zach found
##Enter name to search for or 'none' to terminate program:Jalan
##2
##Jalan found
##Enter name to search for or 'none' to terminate program:Donny
##1
##Donny found
##Enter name to search for or 'none' to terminate program:Adam
##0
##Adam found
##Enter name to search for or 'none' to terminate program:Abie
##0
##Abie not found
##Enter name to search for or 'none' to terminate program:Carla
##1
##Carla not found
##Enter name to search for or 'none' to terminate program:Ed
##2
##Ed not found
##Enter name to search for or 'none' to terminate program:Roger
##3
##Roger not found
##Enter name to search for or 'none' to terminate program:Zap
##4
##Zap not found
##Enter name to search for or 'none' to terminate program:Zyss
##5
##Zyss not found