Binäre Suche (Halbierung) in Python

176

Gibt es eine Bibliotheksfunktion, die eine binäre Suche in einer Liste / einem Tupel durchführt und die Position des Elements zurückgibt, wenn es gefunden wird, und 'False' (-1, None, etc.), wenn nicht?

Ich habe die Funktionen bisect_left / right im bisect-Modul gefunden , aber sie geben immer noch eine Position zurück, auch wenn das Element nicht in der Liste enthalten ist. Das ist für den beabsichtigten Gebrauch vollkommen in Ordnung, aber ich möchte nur wissen, ob ein Element in der Liste enthalten ist oder nicht (ich möchte nichts einfügen).

Ich habe darüber nachgedacht, zu verwenden bisect_leftund dann zu überprüfen, ob das Element an dieser Position dem entspricht, was ich suche, aber das scheint umständlich zu sein (und ich muss auch Grenzen prüfen, ob die Anzahl größer sein kann als die größte Zahl in meiner Liste). Wenn es eine schönere Methode gibt, würde ich gerne davon erfahren.

Bearbeiten Um zu verdeutlichen, wofür ich dies benötige: Ich bin mir bewusst, dass ein Wörterbuch dafür sehr gut geeignet wäre, aber ich versuche, den Speicherverbrauch so gering wie möglich zu halten. Meine beabsichtigte Verwendung wäre eine Art Doppel-Nachschlagetabelle. Ich habe in der Tabelle eine Liste von Werten und muss in der Lage sein, auf die Werte basierend auf ihrem Index zuzugreifen. Außerdem möchte ich in der Lage sein, den Index eines bestimmten Werts oder None zu finden, wenn der Wert nicht in der Liste enthalten ist.

Die Verwendung eines Wörterbuchs hierfür wäre der schnellste Weg, würde jedoch den Speicherbedarf (ungefähr) verdoppeln.

Ich habe diese Frage gestellt, weil ich dachte, ich hätte etwas in den Python-Bibliotheken übersehen. Es scheint, dass ich meinen eigenen Code schreiben muss, wie Moe vorgeschlagen hat.

rslite
quelle
1
Was versuchst du zu erreichen? Wenn die Werte eindeutig sind, sollten Sie eine Menge und "Wenn Wert in Menge: etwas" verwenden.
Kirk Strauser
Für das, was es wert ist, wird "-1" als wahr angesehen; "0" wäre falsch.
Glyphe
3
Ich habe -1 erwähnt, weil eine Funktion, die den Index des gesuchten Elements im Array zurückgibt, bereits 0 zurückgeben kann, sodass -1 zurückgegeben wird, wenn das Element nicht gefunden wird (ähnlich wie bei der Teilstringsuche).
Rslite
3
Wenn Sie numpy verwenden, np.searchsortedist dies nützlich. docs.scipy.org/doc/numpy/reference/generated/…
Roman Shapovalov

Antworten:

237
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
Dave Abrahams
quelle
10
@volcano Binsearch im Allgemeinen auch.
cubuspl42
4
@ TomSwirly nicht so einfach wie deins, aber richtig und immer noch eine Verbesserung:if hi is None: hi = len(a)
Mark Ransom
Was ist mit absteigender Reihenfolge?
Parikshit Chalke
2
Können Sie eine Erklärung außerhalb des Codes hinzufügen? Die Standards hier haben sich geändert.
SS Anne
54

Schauen Sie sich den Code für bisect_left / right an und passen Sie ihn an Ihren Zweck an.

so was:

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
Moe
quelle
29
Ich habe das ursprünglich + 1'ed, aber jetzt bin ich zu dem Schluss gekommen, dass dies keine gute Sache ist. Wenn diese Antwort befolgt wird, führt dies zu einer starken Codeduplizierung, und wie wir alle wissen, ist es wirklich einfach, die binäre Suche zu starten.
Abyx
1
sollte es nicht hi = mid - 1in der sein elif?
Paweł Prażak
7
@ Paweł: Es handelt sich um zwei äquivalente Varianten, je nachdem, ob die Obergrenze inklusive oder exklusiv ist. Sie können hi = midzu hi = mid-1und hi = len(a)zu hi = len(a)-1und while lo < hi:zu ändern while lo <= hi, und es wäre gleichwertig korrekt
user102008
2
Warum nicht so etwas tun wie: def binary_search (a, x, lo = 0, hi = None): i = bisect (a, x, lo, hi) gibt i zurück, wenn a [i] == x else -1 Entschuldigung für die Formatierung - nicht sicher, wie man das richtig macht im Kommentarbereich
Vitali
1
Sie sollten bisect.bisect_left()eher als diese verwenden.
Alastair
37

Dies ist ein wenig abseits des Themas (da Moes Antwort auf die Frage des OP vollständig zu sein scheint), aber es könnte sich lohnen, die Komplexität Ihres gesamten Verfahrens von Ende zu Ende zu betrachten. Wenn Sie etwas in einer sortierten Liste speichern (wo eine binäre Suche hilfreich wäre) und dann nur auf Existenz prüfen, entsteht etwas (im schlimmsten Fall, sofern nicht anders angegeben):

Sortierte Listen

  • O (n log n), um die Liste zunächst zu erstellen (wenn es sich um unsortierte Daten handelt. O (n), wenn sie sortiert sind)
  • O (log n) Lookups (dies ist der binäre Suchteil)
  • O (n) Einfügen / Löschen (kann je nach Muster O (1) oder O (log n) Durchschnittsfall sein)

Während mit einem set(), Sie entstehen

  • O (n) zu erstellen
  • O (1) Nachschlagen
  • O (1) Einfügen / Löschen

Eine sortierte Liste bringt Ihnen wirklich "nächste", "vorherige" und "Bereiche" (einschließlich Einfügen oder Löschen von Bereichen), die bei einem Startindex O (1) oder O (| Bereich |) sind. Wenn Sie diese Art von Vorgängen nicht häufig verwenden, ist das Speichern als Sets und das Sortieren für die Anzeige insgesamt möglicherweise besser. set()In Python entsteht nur sehr wenig zusätzlicher Aufwand.

Gregg Lind
quelle
7
Es gibt noch eine andere Sache, die eine sortierte Liste Ihnen bringt. O (n) geordnete Durchquerung. Mit einem Satz, der O (n log n) ist, müssen Sie am Ende Verweise auf die Daten in eine Liste kopieren.
Omnifarious
1
Wahr genug! Vielen Dank, dass Sie das erweitert haben, was ich unter Bereichssuche verstanden habe. Fwiw, eine vollständige Durchquerung ist die gleiche eine Bereichsabfrage zwischen min, max, die O (k) ist, wobei k = n :)
Gregg Lind
14

Es könnte erwähnenswert sein, dass die bisect-Dokumente jetzt Suchbeispiele enthalten: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Das Erhöhen von ValueError anstelle von -1 oder None ist pythonischer - list.index () tut dies zum Beispiel. Aber natürlich können Sie die Beispiele an Ihre Bedürfnisse anpassen.)

Petr Viktorin
quelle
11

Am einfachsten ist es, die Halbierung zu verwenden und eine Position zurück zu überprüfen , um festzustellen , ob der Gegenstand vorhanden ist:

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
Imran
quelle
2
Schön, aber der Code wird angezeigt, wenn Sie den Wert 'hi' nicht übergeben. Ich würde es so schreiben: "def binary_search (a, x, lo = 0, hi = None): vom Halbierungsimport bisect i = bisect (a, x, lo, hi oder len (a)) return (i- 1 wenn a [i-1] == x else -1) "und teste es wie folgt:" für i im Bereich (1, 20): a = Liste (Bereich (i)) für aa in a: j = binary_search (a, aa) wenn j! = aa:
drucke
8

Dies ist direkt aus dem Handbuch:

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

8.5.1. Suche nach sortierten Listen

Die obigen bisect () -Funktionen sind nützlich, um Einfügepunkte zu finden, können jedoch für allgemeine Suchaufgaben schwierig oder umständlich zu verwenden sein. Die folgenden fünf Funktionen zeigen, wie Sie sie in Standard-Lookups für sortierte Listen umwandeln können:

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

Mit der geringfügigen Änderung sollte Ihr Code also 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
arainchi
quelle
6

Ich bin damit einverstanden, dass die Antwort von @ DaveAbrahams mit dem Halbierungsmodul der richtige Ansatz ist. In seiner Antwort erwähnte er kein wichtiges Detail.

Aus den Dokumenten bisect.bisect_left(a, x, lo=0, hi=len(a))

Das Halbierungsmodul erfordert nicht, dass das Sucharray vorab berechnet wird. Sie können die Endpunkte einfach bisect.bisect_leftmit den Standardeinstellungen von 0und präsentieren len(a).

Noch wichtiger für meine Verwendung ist die Suche nach einem Wert X, so dass der Fehler einer bestimmten Funktion minimiert wird. Dazu brauchte ich eine Möglichkeit, dass der Algorithmus von bisect_left stattdessen meine Berechnung aufruft. Das ist wirklich einfach.

Geben Sie einfach ein Objekt an, das definiert __getitem__ alsa

Zum Beispiel könnten wir den Halbierungsalgorithmus 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)
paulluap
quelle
Das ist nicht sauber. Verwenden Sie scipy.optimizedazu.
Neil G
4

Wenn Sie nur sehen möchten, ob es vorhanden ist, versuchen Sie, die Liste in ein Diktat umzuwandeln:

# 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 Computer dauerte "wenn n in l" 37 Sekunden, während "wenn n in d" 0,4 Sekunden dauerte.

jrb
quelle
2
Dies ist aus mehreren Gründen nicht immer eine gute Option: 1) Diktate / Sets beanspruchen mehr Speicher. 2) Wenn er nicht viel in der Liste hat, kann eine binäre Suche schneller sein. 3) Das Konvertieren der Liste in ein Diktat ist eine O (n) -Operation, während eine binäre Suche O (log n) ist.
Jason Baker
3
Als FYI ist der "Set" Overhead in Python im Vergleich zu Python-Listen sehr, sehr gering. Und sie sind extrem schnell für Suchvorgänge. Wo die binäre Suche wirklich hervorragend ist, ist das Nachschlagen von Bereichen.
Gregg Lind
Das Konvertieren der Liste kann O (n) sein, aber das Sortieren der Daten in der Liste, was Sie vor der binären Suche tun müssten, ist schlechter. Woher kommen die Daten? Sie können sie wahrscheinlich unterwegs in ein Wörterbuch einfügen. Ich bin damit einverstanden, dass die Erinnerung ein Problem sein kann.
Mark Baker
4

Dieser ist:

  • nicht rekursiv (was es speichereffizienter macht als die meisten rekursiven Ansätze)
  • tatsächlich arbeiten
  • schnell, da es ohne unnötige Wenn und Bedingungen läuft
  • basierend auf einer mathematischen Behauptung, dass der Boden von (niedrig + hoch) / 2 immer kleiner als hoch ist, wobei niedrig die untere Grenze und hoch die obere Grenze ist.

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
Mateusz Piotrowski
quelle
Können Sie die Testfälle teilen?
Lebensbalance
2

Die Lösung von Dave Abrahams ist gut. Obwohl ich es minimalistisch gemacht hätte:

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

Während es in Python keinen expliziten binären Suchalgorithmus gibt, gibt es ein Modul bisect, mit dem die Einfügemarke für ein Element in einer sortierten Liste mithilfe einer binären Suche ermittelt werden kann. Dies kann dazu gebracht werden, eine binäre Suche durchzuführen. Der größte Vorteil davon ist der gleiche Vorteil, den der meiste Bibliothekscode hat - er ist leistungsstark, gut getestet und funktioniert einfach (insbesondere die erfolgreiche Implementierung von Binärsuchen kann recht schwierig sein - insbesondere, wenn Randfälle nicht sorgfältig werden).

Grundtypen

Für Grundtypen wie Strings oder Ints ist es ziemlich einfach - alles, was Sie brauchen, ist das bisectModul und eine sortierte Liste:

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

Sie können dies auch verwenden, um Duplikate zu finden:

...
>>> 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']

Natürlich können Sie bei Bedarf auch nur den Index und nicht den Wert an diesem Index zurückgeben.

Objekte

Bei benutzerdefinierten Typen oder Objekten sind die Dinge etwas schwieriger: Sie müssen sicherstellen, dass umfangreiche Vergleichsmethoden implementiert werden, damit die Halbierung korrekt verglichen werden kann.

>>> 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']

Dies sollte mindestens in Python 2.7 -> 3.3 funktionieren

stephenfin
quelle
1

Wenn Sie ein Diktat verwenden, möchten Sie Ihren Speicherbedarf nicht verdoppeln, es sei denn, die von Ihnen gespeicherten Objekte sind wirklich winzig, 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 wird 'foo' nur einmal gespeichert. Macht das einen Unterschied für Sie? Und über wie viele Dinge sprechen wir überhaupt?

Kirk Strauser
quelle
Es geht um Zahlen und viele davon :) Ich würde gerne ein Array verwenden, das fast so groß ist wie der Computerspeicher. Ich weiß, dass die Basis meines Problems falsch sein könnte, aber ich war neugierig auf das Fehlen einer binären Suchmethode.
Rslite
1
Sie können kein Schlüsselobjekt haben, das klein genug ist, um hier als "wirklich winzig" zu gelten. Ein Objekt hätte einen Mindestpreis von 3 Wörtern (Typ, Nachzählung, Nutzlast), während eine Liste 1 Wort, eine Menge 1 Wort und ein Dikt 2 Wörter hinzufügt. Alle drei (Liste / Menge / Diktat) weisen den Raum ebenfalls auf irgendeine Weise vor, was ein weiterer Multiplikator ist, aber immer noch nicht ausreicht, um eine Rolle zu spielen.
Rhamphoryncus
1

Dieser Code arbeitet rekursiv mit Ganzzahllisten. Sucht nach dem einfachsten Szenario: Listenlänge kleiner als 2. Dies bedeutet, dass die Antwort bereits vorhanden ist und ein Test durchgeführt wird, um die richtige Antwort zu finden. Wenn nicht, wird ein mittlerer Wert eingestellt und auf die Richtigkeit geprüft. Wenn dies nicht der Fall ist, wird die Halbierung durchgeführt, indem die Funktion erneut aufgerufen wird, der mittlere Wert jedoch als obere oder untere Grenze festgelegt wird, indem er nach links oder rechts verschoben wird

def binary_search (intList, intValue, lowValue, highValue):
    if (highValue - lowValue) <2:
        return intList [lowValue] == intValue oder 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)
rct
quelle
1

Schauen Sie sich die Beispiele auf Wikipedia an: 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
jdsantiagojr
quelle
0
'''
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 korrigiere mich :). Danke dir

iraycd
quelle
0
  • s ist eine Liste.
  • binary(s, 0, len(s) - 1, find) ist der erste Anruf.
  • Die Funktion gibt einen Index des abgefragten Elements zurück. Wenn es keinen solchen Artikel gibt, wird er zurückgegeben -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)
AV94
quelle
0
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
user3412550
quelle
0

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)

// Um ​​die obige Funktion aufzurufen, benutze:

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))
jitsm555
quelle
0

Ich brauchte eine binäre Suche in Python und generisch für Django-Modelle. In Django-Modellen kann ein Modell einen Fremdschlüssel für ein anderes Modell haben, und ich wollte eine Suche nach den abgerufenen Modellobjekten durchführen. Ich habe folgende Funktion geschrieben, die Sie verwenden können.

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
sonus21
quelle
0

Viele gute Lösungen oben, aber ich habe keine einfache (KISS halte es einfach (weil ich bin) dumme Verwendung der in Python eingebauten / generischen Halbierungsfunktion gesehen, um eine binäre Suche durchzuführen. Mit ein bisschen Code um die Halbierungsfunktion herum, Ich glaube, ich habe unten ein Beispiel, in dem ich alle Fälle auf ein kleines String-Array von Namen getestet habe. Einige der oben genannten Lösungen spielen darauf an / sagen dies, aber hoffentlich hilft der einfache Code unten jedem, der so verwirrt ist wie ich.

Python-Halbierung wird verwendet, um anzugeben, wo ein neuer Wert / ein neues Suchelement in eine sortierte Liste eingefügt werden soll. Der folgende Code verwendet bisect_left, der den Index des Treffers zurückgibt, wenn das Suchelement in der Liste / im Array gefunden wird. (Beachten Sie, dass bisect und bisect_right den Index des Elements nach dem Treffer oder der Übereinstimmung als Einfügemarke zurückgeben.) Wenn nicht gefunden , bisect_left gibt einen Index zum nächsten Element in der sortierten Liste zurück, der den Suchwert nicht ==. Der einzige andere Fall ist, wo das Suchelement am Ende der Liste steht, wo der zurückgegebene Index über dem Ende der Liste / des Arrays liegt und was im Code unter dem frühen Beenden von Python mit "und" Logikhandles. (erste Bedingung False Python überprüft keine nachfolgenden Bedingungen)

#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
Bob
quelle