例えば、本棚から特定の1冊の辞書を探す場合を考えます。端から順番に1冊ずつ探す方法（線形探索）では、本がN冊あると最大でN回の確認が必要です。この場合の計算量は「O(N)」と表されます。一方で、辞書が五十音順に並んでいることを利用して、真ん中のページを開いて半分ずつ絞り込んでいく方法（二分探索）では、最大でも「O(log N)」という非常に少ない回数で探し出すことができます。

もう少し詳しく