たとえば、{0,9}、{14,18}、{19,30}などの数値の範囲のリストがあるとします。
そして、番号Nがリストに含まれているかどうかを確認したいと思います。N = 15の場合、15は{14,18}の範囲にあるため、答えはyesになります。N= 11の場合、11はリスト内のこれらの範囲にないため、答えはnoになります。
私の質問は：そのような問題への答えを決定するための効率的な方法はありますか？
ありがとう
2 に答える
3
範囲のリストを並べ替えてから、重複する範囲を結合すると、バイナリ検索で問題を解決できます。これは、O（log（N））です。ここで、Nはリスト内の要素の数です。
範囲を並べ替えて結合した後、範囲リストを配列に入れることができます。たとえば、{a、b}、{c、d}は（a、b、c、d）になり、バイナリ検索後にあなたの数が偶数と奇数の位置を持つ要素の間にあるかどうかをチェックするかもしれません、そしてあなたの数は範囲内にあります、さもなければそれは外れています。
二分探索では、並べ替えられた配列があるため、配列を2つの等しい部分に分割し、キー値を部分を分離する配列値と比較してから、上部または下部を選択して何度も分割することができます。
二分探索を使用せず、リストがソートされていない場合は、毎回すべての要素を調べる必要があります。これはO（N）であり、非常に非効率的であると見なされます。
より詳細な説明が必要な場合は、コメントを残してください。
于 2012-05-04T09:24:56.937 に答える
2
範囲のリストが動的に変化する場合、区間木は探しているデータ構造です。
于 2012-05-04T09:35:50.897 に答える