質問: 二分探索(二分検索orバイナリサーチ)の計算量のlog2nが理解できません。
回答: 計算式だけで考えてもおそらく見えてきません。 イメージは、 ABCDEFGHIJの10文字からJを見つけるには ↓ 1回)FGHIJ ↓ 2回)HIJ ↓ 3回)IJ ↓ 4回)J 10 -> 5 -> 3 -> 2 -> 1 1文字に絞り込むまでに何回2分割しないといけないのか?、で 逆に言えば 10文字あっても12文字あっても 10 -> 5 -> 3 -> 2 -> 1 12 -> 6 -> 3 -> 2 -> 1 回数は同じです。 が、20文字あると違う。 20 -> 10 -> 5 -> 3 -> 2 -> 1 この考えを整理すると、 1→2→4→8→16→32→・・・・と 2の何乗で表現できる桁かがわかれば、その何回2分割かが見えてきます。 アイテムが4つあれば、4-2-1、2回となる。 4のときは2の2乗だから計算量は2。 競技のトーナメント方式で何回戦まで必要か、何回勝てば優勝か、と考え方が似ています。 4チームいれば普通は2回勝てば優勝、です。 ----- 求めるための「結果式」よりも、求める「過程」を大事にすると良いです。