範囲を含む配列のバイナリ検索

Question

配列がこのような要素を含んでいるとします。

[1,2,5,6,8,9,11-13]、2-5はa 2、3、4、5を表す範囲で、「4」を見つけたい場合はインデックス1（0から始まる）が必要な答えです。

constansスペースとlog（n）時間のこのタイプの要素のようなバイナリ検索を適用することは可能でしょうか？

Answer 1

バイナリ検索を使用すると、コンセプトは魅力のような範囲でも機能します。実際には、これは時間と空間の複雑さを減らすために一般的に使用される概念です（たとえば、gap encoding）。 しかし、ライブラリメソッドはおそらく範囲を受け入れないため、ライブラリを使用する代わりに独自に書き込む必要があります。

---

私たちは簡単にインデックスである値探し[1, 2-5, 6, 8-9, 11-13]のあなたの与えられた入力のバイナリ検索を実行して行きましょう。

配列[1, 2-5, 6, 8-9, 11-13]が長を有し、我々はある中央にインデックスの決定します。値6が読み込まれます。値4を検索して、検索を続けます。

現在、[1, 2-5, 6]に検索間隔を減少長、我々はミドルインデックスで決めます。それは2-5と読みます。 4がその範囲内にあるので、結果としてインデックスを返します。

例えばそれは、が内側5-7ないとして、その後、我々は左に検索を続けるだろうが5-7を読みたい場合。同様に、1-3と表示されている場合は、検索を続けます。ここで

---

は、いくつかの擬似コードとバイナリサーチの説明です：Binary search algorithm at Wikipedia

あなたがちょうどあなたの質問を編集し、あなたがこれまでにやっている私たちを見るよりも、実装に問題がある場合は、我々はその後、適応すると、助けて。