最近また競技プログラミングを勉強していて、AtCoderで100問これ解けみたいなので復習しているが、10年ぶりぐらいに考えると、二分探索ですらゼロイチで組み立てるのは結構難しかった。
もちろんロジックは分かるし、紙で書いたら実装できてるんだが、左端と右端を変数に置いておくというのをなぜか思いつかず、ものすごく捏ね繰り回した計算をしてしまっていた。
切り捨て除算や、値が見つからない時どうする(どう探索を終える)のかとか、思ったより躓いたので、自分の才能の無さは置いておくとして、また勉強してよかったし、度々復習しておこうと思った。
のだが、実際はこんなロジックを頭に入れておくことはないのかもしれない。二分探索自体を本番で実装することはないし、「二分探索どうやるんだっけかな」と調べれば速攻で見つかるし理解できるのだから。
よく言われる、
It's not what you know (何を知っているのかではなく)
It's who you know (誰を知っているかだ)
のように、どう調べればどの情報が出てくるか、を知っていればそれでいいのではないかとも思う。
ただ自分の知識として、二分探索ぐらいはさくっと出せるようにしておきたい。ひょっとしたらそれがプログラムを好き、ということかもしれない。
T = list(map(int, input().split())) X = list(map(int, input().split())) T = sorted(T) for v in X: L = 0 R = len(T) - 1 M = (L + R) // 2 while L <= R: if T[M] == v: print("hit") break if T[M] > v: R = M - 1 else: L = M + 1 M = (L + R) // 2 else: print("miss")