3

Javaでソートされた文字列配列があります。その配列でユーザー指定の文字列で始まる最初の要素を見つけようとしています。最初は二分探索かと思ったのですが、ユーザーが指定した文字列で始まる文字列ではなく、等しい文字列を見つけてしまいます。やりたいことを達成できるようにするには、バイナリ検索をどのように変更すればよいですか?

4

1 に答える 1

6

バイナリ検索では、要素が存在しない場合に「目的の要素よりも小さい最後の要素」を見つけることができます（「挿入する必要のあるインデックス」と呼ばれることもあります）。

この機能を使用してバイナリ検索を実行すると、要素を見つけて確認できます。

  1. それが正確な要素である場合、これはこの接頭辞を持つ配列の最初の要素です。これは、この接頭辞を持つ「最小の」要素であり、これで完了です。
  2. 同じ要素ではない場合（1つ増やすと）、「目的の要素よりも大きい最小の要素」が得られます。この要素は、この接頭辞が付いた配列の最初の要素です（配列に接頭辞がある場合）。

この機能は非常に一般的です。たとえば、Javaに存在しArrays.binarySearch()ます。javadocsから：

戻り値：検索キーのインデックス（配列に含まれている場合）。それ以外の場合（-（挿入点）-1）。挿入ポイントは、キーが配列に挿入されるポイントとして定義されます。つまり、キーよりも大きい最初の要素のインデックスです。

見つかったインデックスから、目的の要素を簡単に見つけることができます。

コードスナップ：

String[] arr = { "aa" , "bb","c", "cc" , "ccc", "cccc", "ddD" };
int idx = Arrays.binarySearch(arr, "c");
if (idx < 0) 
    System.out.println(arr[-1 * idx - 1]);
else System.out.println(arr[idx]);
于 2012-10-21T11:43:39.840 に答える