binary-search - 二分探索の質問

Question

バイナリ検索の場合、ファイル内のレコードを見つけるために必要な比較の平均数はいくつですか？

Answer 1

これは宿題だと思いますので、正直な答えではなくヒントを提供します。また、大きなOの答えだけでなく、比較的正確な答えを見つけるように求められたと仮定します。

このように考えてください。比較を行うたびに、検索スペースが半分になります。検索スペースのサイズがSの場合、次の反復でレコードが見つかる確率は1/Sです。Cが比較の数を表す場合、P（比較Cで検索）= P（<C比較で検索しない）* P（比較Cで検索| <C比較で検索しない）。