手を動かしてコードを書くことの重要さを再確認

19/05/13の日記。

土日はほとんど勉強をしていなかったが平日に戻ったこともあり、今日は進捗を産むことができた。

どんな進捗かというと、プログラミングコンテストチャレンジブック（通称：蟻本）を読み進めた。はじめの1章だけだが。

はじめの1章はウォーミングアップということで、難しい概念は出てこなかった。最も難しかった内容が2分探索だろうか。

しかし、それを実装しようとすると話は全く別だった。

二分探索はかなり前にC言語で実装したことはあったものの、そのときの記憶がほとんどないため、また、今回使ったPythonでは実装は初めてだったため、かなり苦戦した。Python経験のなさを痛感させられた。

手を動かして確認することの重要性を侮っていた。二分探索は頭で理解しているからと舐めていた。

反省し、明日以降に活かさないといけない。

（自分用のメモのようなもの）

今日実装した二分探索はループを使ったものだった。再帰を使った場合や、bisect（詳しくはhttps://docs.python.org/ja/3/library/bisect.html#searching-sorted-lists）を使った場合なども実装したい。

また、今回の問題の制約では影響はないが、以下のウィキペディアの二分探索の項にある以下の記述も頭に入れておきたい。

実装上の間違い
ドナルド・クヌースは "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" と述べており[1]、二分探索が正確に実装されていないことは多い。Richard E. Pattis の1988年の調査では、書籍20冊のうち15冊が誤っていた[2]。
良くある間違いの一つは、imin + (imax - imin) / 2 を (imax + imin) / 2 としてしまう事である。これでは、imax + imin が int の限界を超えてオーバーフローしてしまう可能性がある。Java の標準ライブラリの Arrays.binarySearch() では JDK 1.2 (1998年) から間違えており、Java 6 (2006年) で修正された[3]。
ーウィキペディア「二分探索」（https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2）より