ソートされた配列内でnに最も近い値を見つける、並べ替えられた配列

Question

この問題に対して、私はソートされた2倍の配列を持っています。私は、nに最も近い値のインデックスを素早く効率的に見つけることができる必要があります。効率は重要です。割り当て状態はO（log n）で行うことができます。そのため、ある種の変更されたバイナリ検索で行うことができます。

私はこれまでに尋ねられたことは知っていますが、私が見つけたすべての回答は、並べ替えられていない配列を想定していました。

ご了承ください。ありがとうございました。

Answer 1

はい、変更されたバイナリ検索で行うことができます。いつものように番号を探してください。

• あなたがチェック最後の番号が下であれば、あなたがそれを見つけた場合、あなたがそれを見つけていない場合、それは
• 正しい数（クローズではなくオーバー）だ、それは（あなたの番号だあなたはすでにました上記の数字を一度見て、それが高すぎると感じた場合）
• 最後に見つかった番号と最後の番号が終わった場合、最高のものを見つける方法がわかります。

はあまりにも考慮すべきいくつかのエラー条件があることを覚えて、あなたはバイナリ検索と間違って何罰金:)