配列にない部分配列の助けを借りて数を求める対数時間アルゴリズム

問題は次のとおりです。

Given: A sorted array A of n integers where
A[n − 1] − A[0] ≥ n.

Asked: Give an algorithm and the invariant of the algorithm that
finds a number between A[0] and A[n – 1] that does not
appear in the array A. The algorithm must use logarithmic time.

私はこの問題にどのように接近するのか、そしてどのようなステップを取るべきか考えていない。バイナリ検索とは関係がありますが、これ以上は得られませんでした。

ベストアンサー

問題について考える方法は次のとおりです。

やや単純化したバージョンを扱いますが、一般化するのは簡単です。 $ A [0] = 0 $と$ A [n-1] = n $を$
A [i ^ {*}]のような$ A $のユニークなインデックスとすると、 -A [i ^ {*} – 1] geq2
$(ここでは、{$ 0,1、 dots、n $}の範囲に$ A $にない要素が1つしかないと仮定します)。

Look at the median value of A suppose that $A[lceil n/2
rceil]> lceil n/2 rceil $ what does this tell you about
$i^{*}$ Is it possible that $i^{*}$ is in the latter half of
$A$?

あるいは、$ A [ lceil n/2 rceil] = lceil n/2 rceil $(これは、$ A
$に関する私たちの仮定に基づく唯一の他の選択肢です)。 $ i ^ * $が配列の前半にある可能性はありますか?

Note that, in this case, asking “Is $A[lceil n/2 rceil]>
lceil n/2 rceil $?”

Is the same as asking “Is $A[lceil n/2 rceil] – A[0]>
lceil n/2 rceil $?”

これを任意のリストに一般化できますか?

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です