問題タブ [binary-search]

n のバイナリ表現に従って、n 個の要素を格納するために、それぞれの長さが 2^k の複数の配列を使用するという考え方です。

上記のデータ構造では、SEARCH は各配列のバイナリ検索のシーケンスによって実行されます。INSERT は、空の配列に到達するまで、同じ長さの配列の一連のマージによって実行されます。

詳細:長さ 2^k の垂直配列があり、その配列の各ノードに長さ 2^k の水平配列が接続されているとします。

つまり、垂直配列の最初のノードには、長さ 2^0=1 の水平配列が接続され、垂直配列の 2 番目のノードには、長さ 2^1= 2 の水平配列が接続されます。したがって、挿入は最初の水平配列で最初に実行され、2 番目の挿入では最初の配列は空になり、2 番目の水平配列は 2 つの要素でいっぱいになり、3 番目の挿入では 1 番目と 2 番目の配列水平になります。配列が満たされているなどです。次のように、検索と挿入の通常のバイナリ検索を実装しました。

上記のように機能する動的二分探索を実装するために、このプログラムまたは新しいプログラムを変更する方法を誰か提案してください!!

非常に大きなテキストファイル（10GBの場合もあります）でバイナリ検索を実行するために使用できるライブラリはありますか？

このファイルは一種のログファイルです。すべての行は日付と時刻で始まります。したがって、行は順序付けられます。

二分探索の再帰関数を作成します。
この関数は、ソートされた配列と検索する項目を受け入れ、項目のインデックス (項目が配列内にある場合) または -1 を返します (項目が配列内にない場合)。
さらに、関数をテストするテスト プログラムを作成します。

http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance

検索しようとしている整数が常に配列内にある場合、バイナリ検索アルゴリズムの平均パフォーマンスを計算できるプログラムを作成するのを手伝ってくれる人はいますか?

編集：実際にプログラムを実行して呼び出し回数を数えることでこれを実行できることはわかっていますが、ここでやろうとしていることは、関数を呼び出さずに実行することです。

edit2: KennyTM: それは時間の複雑さです。呼び出しの平均数を計算しようとしています。たとえば、A[2] で整数を検索する平均呼び出し回数は、1.67 (5/3) になります。

問題：

これにはJava Tutorials™</a> ソースコードを使用しています。これがソースコードです。

私はこれを試しました：

そしてそれは完全に機能します。ただし、これを使用すると：

dce_ifaceと入力すると表示されますdceが、入力_してからoorを入力すると、オフセットがリストのどこから来るかsなどの別のものが表示されます。dce_offsetwords.add("fragoffset");

この問題を解決するにはどうすればよいですか? 前もって感謝します。

ローテーションされたソート済みリストがあり、そのリストでバイナリ検索を実行して最小要素を見つけたいと考えています。

最初のリストが{1,2,3,4,5,6,7,8}であると仮定しましょう。ローテーションされたリストは{5,6,7,8,1,2,3,4}のようになります

この場合、通常の二分探索は機能しません。これを行う方法についてのアイデア。

- 編集

私は別の条件を持っています。リストがソートされていない場合はどうなりますか??

ルックアップとして使用したい文字列の大きな配列があります。

私はを使用していますが、単純なループを実行しているin_array()と思わin_array()れます-アルゴがbsearchアルゴを使用しているかどうかを誰かが知っていますか？

複雑さ以下の循環ソート配列内の特定の要素を検索したいと考えていますO(log n)。
例: を検索13し{5,9,13,1,3}ます。

私の考えは、循環配列を通常の並べ替えられた配列に変換し、結果の配列でバイナリ検索を行うことでしたが、私の問題は、私が思いついたアルゴリズムがO(n)最悪の場合にかかる愚かなことでした:

次に、i 番目の要素の対応するインデックスは、次の関係から決定されます。

私の変換 (循環から通常への) アルゴリズムが O(n) かかる可能性があることは明らかなので、より良いものが必要です。

ire_and_curses のアイデアによると、Java での解決策は次のとおりです。

うまくいけば、これはうまくいくでしょう。

私は赤黒の木を持っており、基本的な操作は挿入、削除、順序通りのトラバース、ポストオーダー、プリオーダーなどです。

指定した値より大きいツリー内のノードを返すことができるメソッドを作成したいと考えています。未満でも同じです。

誰でも疑似コード/アルゴリズムを教えてもらえますか(おそらく同じことを意味します)

乾杯

辞書順でソートされた 2 つの int 値と 1 つの文字列値を含むバイナリ ツリーを作成しようとしていますが、どうすればよいかわかりません。すでにソートされている配列リストを作成しましたが、バイナリツリーはソートされていない参照ベースでなければならず、作成中にリストをソートすることを考えています。誰でもこれを手伝うことができますか？簡単なアイデアをいただければ幸いです。