カテゴリの2Dグリッドで座標を検索するためのベストデータ構造

Question

各要素が水平および垂直座標の制限を格納し、対応する2Dグリッド内の座標を検索したいと考えています。例について

：（15,25）であっても検索する座標せて、グリッド（A、B、C、D、E及びFは戻り値である）である：

(0,0) - (0,10) - (0,20) - (0,30) 
    | [A] | [B] | [C] | 
(10,0) - (10,10) - (10,20) - (10,30) 
    | [D] | [E] | [F] | 
(20,0) - (20,10) - (20,20) - (20,30) 
    | [G] | [H] | [I] | 
(30,0) - (30,10) - (30,20) - (30,30) 

だから我々の座標（15,25）が10-20の間にあり、20-30が横になるので、検索関数は[F]を返すべきです。

このような場合、どのようなデータ構造と検索アルゴリズムが最も複雑なのでしょうか？

注：水平軸と垂直軸の座標の制限は、既に昇順でソートされています。

Answer 1

どのようなデータ構造ですか？

アレイ。

要素が2次元の点などの配列です。これはO（n）, whereです。nはあなたの軸のサイズです。

検索アルゴリズム？ [..]データは既に昇順でソートされています。

Binary Searchを使用してください。

二回、O(logn)に漸近表記を維持するすべての軸のための1つ。もちろん

、あなたは（クエリが15である場合には）20を満たしたときに、クエリが配列中に存在しないことであるかもしれないため、検索を停止しなければなりません。現在の要素がクエリよりも大きいか等しい場合、検索を停止します。

---

PS：グリッドが正方形でない場合は、kdツリーを使用して、「最近傍」を検索してください。

Answer 2

は、当分の間、あなたが実際にあなたのグリッド上で使用している座標を無視し、各軸に沿ってそれらを0,1,2,3,...ラベルを付けます。今すぐ素敵な素敵な配列があります。

次に、実際の座標を前の手順で定義した擬似座標に変換する関数を見つけます。あなたの例では、この関数は単純に整数（または切り捨て）除算を10で割ったものです。座標があまりうまく配置されていない場合は、少し注意する必要があります。あなたはそれを描いています）セルの左上隅。

これで、2つの関数呼び出しと1つの参照を配列に作成する必要があります。この複雑さは、座標から擬似座標に変換するために書く関数の複雑さに依存しますが、kの小さな整数値の場合、O(k)よりもはるかに大きくなることが分かりません。配列内の要素を探すのはO(1)です。