問題タブ [binary-search]

これは、G。MichaelScneiderとJudithL.Gerstingによる教科書InvitationtoComputerScienceからの直接の引用です。

セクション3.4.2の最後で、リストをソートしてからバイナリ検索を使用するのではなく、ソートされていないリストで順次検索を使用することのトレードオフについて説明しました。リストのサイズがn=100,000の場合、比較の数の点で2番目の選択肢が優れている前に、最悪の場合の検索を何回実行する必要がありますか？

質問が何を求めているのか、私にはよくわかりません。

シーケンシャル検索は次数（n）で、バイナリは次数（lgn）であり、いずれの場合もlgnは常にn未満になります。そしてこの場合、nはすでに与えられているので、私は何を見つけることになっています。

これは私の宿題の1つですが、どうしたらよいかわかりません。誰かが私のために平易な英語で質問を説明できますか？

上部にリストされているbinary_search関数に問題があります。どこに行けばいいのかわからない。私は二分探索にあまり精通していません。

完了すると、プログラムはファイルから入力を取得し、それを配列に割り当ててから配列をソートすることを想定しています。この後、バイナリ検索を使用して、ユーザーから指定された番号を見つけ、配列内のその場所をユーザーに表示する必要があります。

更新：見つかったインデックスに対して間違った出力を取得しています.... midindexに1つ追加する必要がありますか？

Objective-cブロックを使用してバイナリ検索を実装しようとしています。関数を使用していますindexOfObject:inSortedRange:options:usingComparator:。これが例です。

前述の関数で外部で定義されたobjective-cブロックをどのように使用できるのでしょうか。これが2つの比較関数です。

これらは、にある次の宣言を参照して記述されていますNSObjCRuntime.h。

配列のソートされた値を検索するために、バイナリ検索よりも高速なアルゴリズムはありますか？

私の場合、A配列内にソートされた値（任意のタイプの値である可能性があります）がnあります。探していた値が次の範囲内にある場合は、返す必要があります。A[n] and A[n+1]

各行にint;int値で構成されたファイルがあります。どちらの列も行ごとに昇順です。次のコードを使用して、そのファイルを配列にロードする予定です。

この配列を使用して、キー $tmp[0] に基づいてバイナリ検索を実行するつもりです。配列には 1000 個の要素がありますが、検索は 10.000 個の異なる値に適用されます。単純に 2x1000 マトリックスを定義して要素をロードする必要がありますか?

どうも

正弦関数のゼロ点を見つけたい。パラメータは区間[a、b]です。二分探索と同じようにする必要があります。

aとbの間の間隔で副鼻腔関数のヌル点を検索する関数を実装します。検索間隔[下限、上限]は、下限と上限が互いに0.0001未満になるまで半分にする必要があります。

これが私のコードです：

return zeropoint（middle、b）;の行で多くのエラーが発生します。

最初のステップでは、区間の最初のゼロ点だけを見つけたいと思います。

何か案は？

同じ要素が存在しない場合はすぐに小さい要素を返し、要素が他のすべての要素よりもすでに小さい場合にのみ NULL を返す bsearch に似たものが組み込まれていますか? これには、戻り値のキーが関数の引数と同じかどうかをユーザーが確認する必要がありますが、それ自体は非常に便利です。ありがとう。

でテストしている要素のイテレータを取得したいbinary-search。boolただし、値が見つかったかどうかを示すのみを返します。イテレータを取得するには？

最近、範囲を2ではなくファイ（黄金比）で分割することで二分探索が改善されるかもしれないという意見を聞きました。そのような最適化について聞いたことがないので、これは私にとって大きな驚きでした。これは本当ですか？2による除算とファイによる除算が同等のパフォーマンスであった場合、これは真実でしたか？

そうでない場合、黄金分割探索が二分探索よりも高速に実行される一般的な条件はありますか？

UPD：関連性のないウィキペディアの記事へのリンクを削除するように編集されました。誤解を招く恐れがあります。

オルタント型の領域が繰り返し切り出された整数格子上の大きな箱の重心を効率的に追跡することに興味があります。私は計算幾何学の文献を探し回っていましたが、関連する可能性のあるさまざまなデータ構造がありますが、ほとんどの議論は可視性の計算 (コンピューター グラフィックスの場合) または最近傍探索 (データ マイニングなどの場合) に関するものです。

論文 http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf、つまり:

「バイナリ空間分割ツリー」によって幾何学的オブジェクトを表し、集合操作をサポートし、集合操作の後にオブジェクトの重心が再計算されるという興味深い言及 (詳細なし) があるシステムについて説明しています。おそらく私には盲点がありますが、ツリー マージ アルゴリズム中に質量の中心を効率的に更新する方法がすぐにはわかりません。また、Naylor のものを引用している論文で質量の中心の計算に関する議論を見つけられませんでした。ポインタはありますか？