複雑さがO（lgn）の指定された数を除いて、ソートされた配列内の要素を検索するアルゴリズムはありますか？
int arr[]={0,1,2,-1,4,8,9,-1,17,32,56,128};
配列をしてみましょうは、指定された数-1除くソートされ、私は、以下の条件を満たした任意のアルゴリズムがあるarray.Soで（指定された数ではない）の要素を検索したいですか？要素は、適切な挿入位置を戻し、アレイ内に存在しない場合
以前の配列で10を検索する場合、戻り値は7になります。
ありがとうございます。
いいえ、すべての数字が-1（指定された番号）である長さnの配列を見てください。今すぐランダムに1つの位置を選択し、他の番号で置き換えます。基本的にはあなたの配列は次のようになります。
[-1, -1, -1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1, -1]
は、今あなたが確定O(log N)要素を使用して、数8の位置を見つけることができる方法はありません。
のでなし、一般的なケースでは、あなたがこのを行うことはできません。しかし、指定された要素の数が本当に小さい場合、私はこの状況に対処するためにバイナリ検索を変更できると信じています。
はい。あなたは-1を検索するために複雑さを加えるだけで、それはO（log n）より小さくなります。
別の配列を使用して、前の配列の-1の位置をマップできます。
O（N）の余分なストレージとO（N）の前処理ステップがあるかどうかによって異なります。
可能であれば、意味のある要素のインデックス（たとえば、-1以外の要素へのポインタの配列）を作成できます。これはO（N）の時間/空間を必要としますが、一度取得すれば、O（log n）の複雑さを持つリアルコレクションを検索するためにifを使うことができます。 。
これは実際にどのように使用されますか？ 1つの要素を除いてソートされた配列を持つのはなぜですか？ – Barmar
@Barmar宿題/インタビュー/プログラミング競技 –
@SalvadorDali明らかに、私はOPにそれを認めたい。 – Barmar