javaで簡単な辞書の二分探索のプログラムを作っているのですが、範囲探索の方法がわかりません。
例えば search book open
との具合に入力するとbookからopenまでの単語を列挙するようにしたいのですが
どのようにすればよろしいですが?
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答3件
0
二分探索の本質を理解されていますか?
ソート済みの配列に対する探索アルゴリズムです。
ソート済みという前提条件がある以上、2つのキーワードで検索をかけて、bookのインデックスがi, openのインデックスがjとすれば、iとjの間の全ての要素が、求めたい要素のはずです。
投稿2016/04/16 14:59
編集2016/04/16 15:00総合スコア907
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
次のメソッドが利用できると思います。
-
[http://dodododo.jp/java/javase_6_docs_ja/api/java/util/Arrays.html#binarySearch(short[], int, int, short)](http://dodododo.jp/java/javase_6_docs_ja/api/java/util/Arrays.html#binarySearch(short[], int, int, short))
-
クラスArrays https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html
...
binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
バイナリ・サーチ・アルゴリズムを使用して、指定された配列の範囲から指定されたオブジェクトを検索します。
...
戻り値
指定された範囲内の配列に検索キーがある場合は検索キーのインデックス。それ以外の場合は(-(挿入ポイント) - 1)
...
このメソッドを使って book を配列の全体から検索します。。
book が見つかった場合は、返り値を start_index に保持しておきます。
book が見つからなかった場合は、返り値 * (-1) - 1 を start_index に保持しておきます。
次に open を配列の全体から検索します
open が見つかった場合は、返り値 を end_index に保持しておきます。
open が見つからなかった場合は、返り値 * (-1) - 2 を end_index に保持しておきます。
配列の start_index から end_index の間の要素が求めるものとなります。
(結果の配列のサイズが 0 になることがあることも考慮する事)
参考:
- Javaで二分探索を使ってリストに要素を挿入する http://zawapro.com/?p=608
投稿2016/04/16 23:38
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。