Bisektionsindexsuche - warum mit len ​​(a) vergleichen?

Question

Also versuche ich Halbierung zu verstehen. Ich verstehe, dass es sich um einen nützlichen, rechensparenden Algorithmus handelt, ich bekomme das allgemeine Konzept dessen, was es tut und wie es es macht. Was ich nicht bekommen, beinhaltet diese Suchfunktion, die es verwendet, genommen von https://docs.python.org/2/library/bisect.html

from bisect import bisect_left  

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 

Könnte jemand bitte genau für mich brechen, was die i! = Len (a) Teil der, wenn Linie tut ? Ich kann es lesen - es überprüft, ob der Einfügungsindex von x der Länge der Liste a entspricht - aber ich kann es nicht verstehen. Warum ist es notwendig? Was würde ohne es passieren?

Ich folge, sagen wir mal x hat einen Insertionsindex größer als die Länge von a, dann x offensichtlich nicht in einem gibt es spuckt den Fehler aus - aber wenn das der Fall ist dann die a [i] == x check stolpert es trotzdem ...?

Danke!

Answer 1

Da Listen indiziert sind aus 0 dann a[i] macht keinen Sinn für i == len(a) machen (das letzte Element hat den Index len(a) - 1). Doing a[i] für solche i wird eine IndexError werfen. Jetzt

wenn bisect_left(a, x) kehren len(a) dann bedeutet es, dass das Element sollte am Ende der Liste, um den Auftrag zu erhalten, hinzugefügt werden.

Auf der anderen Seite, wenn es eine Übereinstimmung für x in a dann

bisect_left(a, x) != len(a) 

weil If x is already present in a, the insertion point will be before (to the left of) any existing entries. Wenn es vor dann offensichtlich der Insertionsindex kleiner oder gleich dem letzten Index sein muss (da im schlimmsten Fall entspricht Element letzten Index haben) und der letzte Index ist len(a)-1, die kleiner als die Länge ist.

Alles in allem wenn bisect_left(a, x) == len(a) dann gibt es keine x in a. Dies ermöglicht uns, das "IndexError Problem", das ich am Anfang erwähnt habe, leicht loszuwerden.

Beachten Sie, dass dies (offensichtlich) nicht für bisect_right gilt. Aber nach der ähnlichen Logik können Sie etwas analoges erreichen: wenn bisect_right(a, x) == 0, dann gibt es x in a. Die Implementierung der index Funktion über bisect_right wäre leider schwieriger, da Sie diese Überprüfung für i == len(a) noch benötigen würden, um eine IndexError zu vermeiden.

Answer 2

Zero-basierte Indizierung. Die i != len(a) ist, den genauen Fall abzufangen, wo i gleich der Länge der Liste ist, in welchem ​​Fall a[i] einen Indexfehler auslösen wird (Listen beginnen bei Index 0 und gehen bis zu len(a) - 1).