配列の最大と最小

2周まわすのは、もったいない

気温の記録から、最低気温と最高気温を知りたいとします。低いほうを探して1周、高いほうを探してもう1周でも答えは出ます。ただし、同じデータを2回読むことになります。

読み込みが重いときや、値が次々と流れてくるときには、2周目を取りにくくなります。1周のあいだに最低と最高の候補を同時に追えば、各値を読むのは一度で済みます。

1周のあいだに、2つのことをやる

今まで見た中の最低値と最高値を、それぞれ覚えておきます。新しい値が来たら、最低より小さければ最低を更新し、最高より大きければ最高を更新します。

例えば気温が12、19、7、15、9の順なら、候補は次のように変わります。

最初の1件を両方の候補にします。残りの各値は最低と最高に1回ずつ比べます。5件なら 2 × (5 - 1) = 8 回の比較です。一般にn件なら 2 × (n - 1) 回なので O(n) です。

2周しても O(n) ですが、1周なら読み直しを省けます。最低と最高の候補は2つだけなので、元の配列を除く追加のメモリは、件数によらず O(1) です。時間の増え方と、メモリの増え方は別に考えます。

0から始めると、答えがずれる

暫定値を0にするのは危険です。すべて氷点より上なら、最低が0のまま残ります。すべて氷点下なら、最高が0のままです。実際には記録されていない値を、答えにしてしまいます。

最初の実データを候補にすれば、この取り違えを避けられます。すでに見た範囲の中に必ずある値から始め、その範囲を1件ずつ広げていく考え方です。

ただし、配列が空なら最初の値を取り出せません。

temps = []
print(temps[0])
# 最初の要素がないため、IndexErrorになる

空の記録では最低も最高も決められません。「データなし」と表示するなど、空の場合を先に分けます。0度という測定値で代用すると、本当に0度だった場合と区別できません。

例題で確かめる

冷凍庫の気温が [-4, -9, -2, -6] と記録されています。最初の-4を両方の候補にします。-9で最低を-9へ更新し、-2で最高を-2へ更新します。-6ではどちらも変わりません。答えは最低-9、最高-2です。最高を0で始めた場合の0は、記録にない誤った値です。