二分インデックス検索 - なぜlen（a）と比較するのですか？

Question

私は二分法を理解しようとしています。私はそれが有用で計算を節約するアルゴリズムであることを知っている、私はそれが何をし、どのようにそれを行うの一般的な概念を得る。 私は何を得ることはありませんが、私は！= LEN（a）の場合はラインの部分がない誰かが私のために分解してもらえまさに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 

から取られ、それを使用して、この検索機能を必要とします？私はそれを読むことができます - それはxの挿入インデックスがリストの長さに等しいかどうかをチェックしますが、私はそれを理解できません。それはなぜ必要なのですか？それがなければ何が起こるだろうか？

私は、xの長さより長い挿入インデックスがあるとしましょう.xが明らかに存在しないので、エラーを吐き出しますが、その場合は[i] == xチェックはとにかくそれをトリップする...？

ありがとうございます！

Answer 1

リストは0から索引付けされているので、a[i]はi == len(a)（最後の要素の索引はlen(a) - 1）には意味がありません。そのようなiに対してa[i]を実行すると、IndexErrorがスローされます。

今bisect_left(a, x)戻りlen(a)場合、それは要素が順序を維持するために端リストのにを加えるべきであることを意味します。次いで、一方

xの一致がaである場合

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

If x is already present in a, the insertion point will be before (to the left of) any existing entriesため。 の前にの場合は、明らかに挿入インデックスは最後のインデックスよりも小さくなければならない（最悪の場合、に一致する要素は最後のインデックスを持つ）。最後のインデックスはlen(a)-1である。

bisect_left(a, x) == len(a)なら、xはaにありません。これは私が最初に述べた "IndexError問題"を簡単に取り除くことを可能にします。

bisect_rightではこれが当てはまります（明らかに）。しかし、類似のロジックに従えば、類似のものに到達することができます。bisect_right(a, x) == 0の場合aにはxがありません。残念なことにindexの機能をbisect_right経由で実装することは、IndexErrorを避けるためにまだi == len(a)のこのチェックが必要になるため、より困難になります。

Answer 2

ゼロベースのインデックス作成。 i != len(a)は、iがリストの長さと等しい正確なケースをキャッチします。この場合、a[i]はインデックスエラーを発生させます（リストはインデックス0から始まり、len(a) - 1まで上がります）。