Binäre Suche (Zweiteilung) in Python

https://stackoverflow.com/questions/212358

03-07-2019
|

Frage

Gibt es eine Bibliothek-Funktion führt eine binäre Suche auf einer Liste/Tupel und die Rückgabe der position des Elements, wenn gefunden, und 'False' (-1, None, etc.) wenn nicht?

Ich fand die Funktionen bisect_left/rechts halbieren-Modul, aber Sie noch zurück, eine position, auch wenn das Element nicht in der Liste.Das ist perfekt feine für Ihre beabsichtigte Verwendung, aber ich möchte nur wissen, ob ein Element in der Liste ist oder nicht (nicht einfügen wollen nichts).

Ich dachte, der Verwendung von bisect_left und dann zu prüfen, ob das Element an dieser position entspricht, was ich Suche, aber das scheint umständlich (und ich auch tun muss, Grenzen zu überprüfen, ob die Zahl größer als die größte Nummer in meiner Liste).Wenn es eine schönere Methode, die ich würde gerne wissen, über es.

Bearbeiten Um zu verdeutlichen, was ich brauche diese für:Ich bin mir bewusst, dass ein Wörterbuch wäre sehr gut geeignet für diese, aber ich bin versucht zu halten, den Speicherverbrauch so gering wie möglich.Mein Verwendungszweck wäre es eine Art Doppel-Wege-look-up-Tabelle.Ich habe in der Tabelle eine Liste von Werten, und ich muss in der Lage sein, auf die Werte zuzugreifen, die basierend auf Ihrem index.Und ich möchte auch in der Lage sein zu finden, der index einen bestimmten Wert oder Keine, wenn der Wert nicht in der Liste.

Mit einem Wörterbuch, denn dies wäre der Schnellste Weg, würde aber (ungefähr) verdoppeln Sie die Speicher-Anforderungen.

Ich wurde gefragt, diese Frage zu denken, dass ich möglicherweise etwas übersehen in den Python-Bibliotheken.Es scheint, ich werde zu schreiben, meine eigenen code, wie Moe vorgeschlagen.

Lösung

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

Andere Tipps

Warum auf den Code schauen nicht für bisect_left / rechts und passen sie Ihren Zweck zu entsprechen.

wie folgt aus:

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

Dies ist ein wenig Off-Topic (seit Moe Antwort auf die Frage des OP komplett scheint), aber es könnte an der Komplexität für die ganze Prozedur von Ende lohnt einen Blick zu beenden. Wenn Sie etwas in einer sortierten Listen sind Speicher (das ist, wo eine binäre Suche helfen würde), und dann nur für Existenz Überprüfung Sie entstehen (Worst-Case, sofern nicht anders angegeben):

sortierte Listen

O (n log n), um zunächst die Liste zu erstellen (wenn es unsortierte Daten ist. O (n), wenn es sortiert)
O (log n) Lookups (dies ist die binäre Such Teil)
O (n) einfügen / löschen (vielleicht O (1) oder O (log n) Durchschnitt Fall sein, auf Ihrem Muster abhängig)

Während bei einem set() Sie entstehen

O (n) erstellen
O (1) Lookup
O (1) Einfügen / Löschen

Die Sache eine sortierte Liste wirklich bekommt man auf „Weiter“, „Zurück“ ist und „Bereiche“ (einschließlich Einfügen oder Löschen von Bereichen), die O (1) oder O (| Bereich |), da ein Startindex . Wenn Sie nicht diese Art von Operationen verwenden oft, dann als Mengen zu speichern und zur Anzeige Sortierung könnte ein besseres Angebot insgesamt sein. set() entsteht sehr wenig zusätzlichen Aufwand in Python.

Es könnte sein, erwähnenswert, dass die bisect docs suchen Beispiele jetzt bieten: http://docs.python.org/library/bisect.html#searching -sortierte-Listen

(Raising Valueerror statt Rückkehr -1 oder Keiner ist mehr pythonic -.. List.index () macht es zum Beispiel Aber natürlich können Sie die Beispiele an Ihre Bedürfnisse anpassen)

bisect und eine Position prüfen, um zu sehen, ob der Artikel ist es:

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

Dies ist direkt aus dem Handbuch:

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

8.5.1. Suche sortierte Listen

Die obige bisect () Funktionen sind nützlich für die Einstichstellen zu finden, sondern können schwierig oder unangenehm sein für die gemeinsame Suche Aufgaben zu verwenden. Die folgenden fünf Funktionen zeigen, wie sie in den Standard-Lookups für sortierte Listen zu transformieren:

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

So mit der leichten Modifikation soll Ihr Code sein:

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

Ich bin damit einverstanden, dass @ DaveAbrahams Antwort die bisect Modul der richtige Ansatz ist. Er erwähnt nicht ein wichtiges Detail in seiner Antwort.

Von der docs bisect.bisect_left(a, x, lo=0, hi=len(a))

Das Halbierungs Modul nicht den Such-Array benötigt vorberechnet vor der Zeit zu sein. Sie können nur die Endpunkte der bisect.bisect_left präsentieren, anstatt sie die Vorgaben von 0 und len(a) verwendet wird.

Noch wichtiger für meine Anwendung, auf der Suche nach einem Wert X, so dass der Fehler einer gegebenen Funktion minimiert wird. Um das zu tun, musste ich einen Weg, die bisect_left Algorithmus zu haben, anstatt meine Berechnung nennen. Das ist wirklich einfach.

Geben Sie einfach ein Objekt, das __getitem__ als a

definiert

Zum Beispiel könnten wir den bisect Algorithmus verwenden, um eine Quadratwurzel mit beliebiger Genauigkeit zu finden!

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)

Wenn Sie wollen einfach nur sehen, wenn es vorhanden ist, versuchen Sie die Liste in eine dict drehen:

# 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

Auf meinem Rechner "wenn n in l" 37 Sekunden dauerte, während "wenn n in d" 0,4 Sekunden dauerte.

Dies ist:

nicht rekursiv (was macht es speichereffizient als die meisten rekursive Ansätze)
eigentlich Arbeit
schnell, da es läuft ohne unnötige , wenn ist Bedingungen
auf eine mathematische Behauptung basiert , die der Boden (low + high) / 2 ist immer kleiner als hoch , wobei niedrig ist die untere Grenze und hoch ist die obere Grenze.
getestet: D

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

Dave Abrahams' Lösung ist gut. Obwohl ich hätte getan haben, es minimalistisch:

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

Zwar gibt es keinen expliziten binären Suchalgorithmus in Python gibt es ein Modul - bisect - entwickelt, um die Einfügemarke für ein Element in einer sortierten Liste finden eine binäre Suche verwenden. Dies kann „ausgetrickst“ in eine binäre Suche durchgeführt wird. Der größte Vorteil ist dies der gleiche Vorteil meisten Bibliothekscode hat - es ist leistungsstark, gut getestet und funktioniert nur (Binärsuchen kann insbesondere sein

ein DIKT würden das Doppelte Speicherauslastung nicht wie es sei denn, die Objekte Sie speichern wirklich winzig sind, da die Werte nur Zeiger auf die tatsächlichen Objekte sind:

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

In diesem Beispiel ‚foo‘ werden nur einmal gespeichert. Macht das einen Unterschied für Sie machen? Und genau wie viele Elemente reden wir eigentlich?

Dieser Code funktioniert mit Integer-Listen in einer rekursiven Weise. Sieht für den einfachsten Fall, nämlich: Listenlänge kleiner als 2. Es bedeutet, die Antwort ist schon da und ein Test durchgeführt wird, für die richtige Antwort zu überprüfen. Wenn nicht, wird ein mittlerer Wert gesetzt und getestet die korrekt zu sein, wenn nicht bisection durch den Aufruf erneut die Funktion ausgeführt wird, aber mittleren Wert als die obere oder untere Grenze einstellen, indem sie sie nach links oder rechts zu verschieben

< p>

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

die Beispiele auf Wikipedia Check out 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

Ich denke, das ist viel besser und effektiver. bitte korrigieren Sie mich :). Danke

s ist eine Liste.
binary(s, 0, len(s) - 1, find) ist der erste Anruf.

Funktion liefert einen Index des abgefragten Artikel. Wenn es keinen solchen Artikel ist gibt es -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

Binäre Suche :

// 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)

// Aufruf der obigen Funktion nutzen :

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))

Ich brauchte binäre Suche in Python und Generika für Django-Modelle. In Django-Modellen kann ein Modell der Fremdschlüssel für ein anderes Modell haben und ich wollte einige Suche auf den abgerufenen Modelle Objekte auszuführen. Ich schrieb folgende Funktion können Sie diese verwenden.

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

Viele gute Lösungen oben, aber ich habe keine einfache (KISS halten Sie es einfach gesehen (weil ich bin) stupid Verwendung des Python eingebaut / generic bisect Funktion eine binäre Suche zu tun. Mit etwas Code um die bisect Funktion, ich glaube, ich habe ein Beispiel unten, wo ich alle Fälle von Namen für eine kleine String-Array getestet werde. Einige der oben genannten Lösungen dieses verweisen auf / sagen, aber hoffentlich unter dem einfache Code wird jemand helfen verwirrt wie ich war.

Python bisect wird verwendet, wo, um anzuzeigen, einen ein neuer Wert / Suchbegriff in eine sortierte Liste einzufügen. Der folgende Code, die bisect_left verwendet, die den Index des Treffers zurück, wenn die Suche Element in der Liste / Array gefunden wird (Anmerkung bisect und bisect_right den Index des Elements nach dem Treffer oder Spiel als Einfügepunkt zurück) Falls nicht gefunden , bisect_left einen Index zum nächsten Element in der sortierten Liste zurück, die nicht den Suchwert == wird. Der einzige andere Fall ist, wo der Suchbegriff am Ende der Liste gehen würde, wo der Index zurückgegeben würde über das Ende der Liste / Array, und die im Code unter dem frühen Ausscheiden von Python mit „und“ Logik Griffen. (Erste Bedingung Falsch Python nicht nachfolgende Bedingungen überprüfen)

#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

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow