線形探索と二分探索の停止条件
探索した位置を記録し、未登録の値や配列の端でも止まる二分探索を学びます。
説明
線形探索は先頭から一つずつ値を調べます。二分探索は整列済みの配列の中央を調べ、大小関係を使って候補を半分ずつに絞ります。未整列の配列では、中央より左に小さい値があるという保証がなく、同じ方法を使えません。
2・4・6・8・10・12・14・16の中から14を探し、両方式が調べる位置を比べます。その後、存在しない9、最小値より小さい値、最大値より大きい値、空の配列と重複値を扱い、見つからない場合も含めて境界を説明します。
1線形探索の記録
比較するたびに添字を記録し、一致すればその添字を返します。最後まで一致しなければNoneです。
def linear(values, target):配列と検索値
visited = []通過位置
for i, value in enumerate(values):先頭から順に比較
visited.append(i)添字を記録
if value == target: return i, visited一致したら終了
return None, visited未発見で終了関数は発見位置と通過した添字を返します。大小関係を使わないため、並びが整列済みでなくても使えます。
214まで順に進む
昇順の8要素から14を探します。最初と最後の値を探した場合の比較回数も表示します。
values = [2, 4, 6, 8, 10, 12, 14, 16]整列済みの配列; linear(values, 14)14の探索経路, [(target, len(linear(values, target)[1])) for target in [2, 16, 9]]検索値ごとの比較回数14は添字6で見つかり、7個を比較します。2なら1回、16と未登録の9は8回です。この実装は整列順を使って早期終了する処理を入れていません。
3半開区間で候補を管理
候補を[lo, hi)で表します。loは含み、hiは含まないので、初期値は0と要素数8です。中央mid=4の値10を調べます。
target = 14; lo = 0; hi = len(values)検索値と候補範囲; mid = (lo+hi)//2中央の添字; (lo, hi, mid, values[mid])範囲・中央・値, values[mid] < target右へ進む条件10は14より小さいため、添字4以下は候補から外せます。次のloをmid+1にし、比較済みの中央も除きます。
4範囲を右へ絞る
候補を[5, 8)にすると中央は6です。この位置に14があるので一致します。
lo = mid+1比較済み中央の次へ; mid = (lo+hi)//2新しい中央; (lo, hi, mid, values[mid]), values[mid] == target中央の値と一致判定二分探索では添字4と6の2個を調べて14へ到達しました。線形探索の7個と比べ、整列順を使って候補を除外できています。
5未発見でも範囲が縮む処理
同じ規則を関数にします。中央が大きければhi=mid、小さければlo=mid+1です。loとhiが一致したとき候補は空になります。
def binary(values, target):二分探索
lo, hi, trace = 0, len(values), []初期範囲と履歴
while lo < hi:候補が残る間
mid = (lo+hi)//2中央
trace.append((lo, hi, mid, values[mid]))比較時の範囲を記録
if values[mid] == target: return mid, trace一致で終了
if values[mid] < target: lo = mid+1左半分と中央を除外
else: hi = mid右半分と中央を除外
return None, trace空になったら未発見各反復で比較済みの中央を除外するので、候補が残る限り範囲が小さくなります。lo=midとしてしまうと1要素だけ残った場合に範囲が変わらず、終了できないことがあります。
69が存在しない場合
10より小さいので左へ進み、6、8と比較します。8より大きいことが分かると、範囲は[4, 4)になって空になります。
binary(values, 9)未登録値と範囲の縮小履歴は[0,8)の10、[0,4)の6、[3,4)の8です。どこにも一致せずNoneになります。空の範囲ではvalues[4]をもう一度読む必要はありません。
7配列の端の値と空配列の探索
範囲の端を検索し、さらに0と18、空配列を試します。空の配列では中央を計算して参照する前にループが終わります。
[(target, binary(values, target)[0]) for target in [0, 2, 16, 18]]両端と範囲外, binary([], 9)空配列2と16は添字0と7、0と18はNoneです。空配列は履歴も空になります。初期のhiをlen(values)にしても、hiそのものを添字として参照しないので範囲外になりません。
8重複値の左右の境界
値4が複数あると、単純な一致検索が返す位置は最初とは限りません。bisect_leftは4以上が始まる位置、bisect_rightは4を超える値が始まる位置を返します。
from bisect import bisect_left, bisect_right境界を求める関数; repeated = [2, 4, 4, 4, 6]重複のある配列; left = bisect_left(repeated, 4); right = bisect_right(repeated, 4)等しい範囲の両端; left, right, repeated[left:right], bisect_left(repeated, 5)範囲と未登録値の挿入位置4の範囲は[1,4)で3個です。5の挿入位置も4ですが、5が存在することは意味しません。挿入位置を検索結果として使うときは、配列内かどうかと値の一致を別に判定します。
まとめ
線形探索は先頭から、二分探索は整列順を使って候補を絞ります。
半開区間ではloを含みhiを含めません。比較済みの中央を除外して範囲を確実に縮めます。
一致する要素の発見と挿入位置の取得は別の処理です。重複や空配列も含めて停止条件を考えます。
操作履歴と解説を振り返れます。
Python 3
def linear(values, target):
visited = []
for i, value in enumerate(values):
visited.append(i)
if value == target: return i, visited
return None, visitedvalues = [2, 4, 6, 8, 10, 12, 14, 16]; linear(values, 14), [(target, len(linear(values, target)[1])) for target in [2, 16, 9]]((6, [0, 1, 2, 3, 4, 5, 6]), [(2, 1), (16, 8), (9, 8)])
target = 14; lo = 0; hi = len(values); mid = (lo+hi)//2; (lo, hi, mid, values[mid]), values[mid] < target((0, 8, 4, 10), True)
lo = mid+1; mid = (lo+hi)//2; (lo, hi, mid, values[mid]), values[mid] == target((5, 8, 6, 14), True)
def binary(values, target):
lo, hi, trace = 0, len(values), []
while lo < hi:
mid = (lo+hi)//2
trace.append((lo, hi, mid, values[mid]))
if values[mid] == target: return mid, trace
if values[mid] < target: lo = mid+1
else: hi = mid
return None, tracebinary(values, 9)(None, [(0, 8, 4, 10), (0, 4, 2, 6), (3, 4, 3, 8)])
[(target, binary(values, target)[0]) for target in [0, 2, 16, 18]], binary([], 9)([(0, None), (2, 0), (16, 7), (18, None)], (None, []))
from bisect import bisect_left, bisect_right; repeated = [2, 4, 4, 4, 6]; left = bisect_left(repeated, 4); right = bisect_right(repeated, 4); left, right, repeated[left:right], bisect_left(repeated, 5)(1, 4, [4, 4, 4], 4)
演習完了