İkili axtarış#3451

İkili axtarış

1 saniyə

64 meqabayt

Çox çətin

İkitərəfli axtarış — sıralanmış massivdə verilmiş elementi tapmaq üçün istifadə olunan bir alqoritmdir. Gəlin ikitərəfli axtarışın aşağıdakı psevdokodunu nəzərdən keçirək ( $/$ tam bölməni göstərir):

giriş: $a_{0}, a_{1}, \dots, a_{n - 1}$ a_0, a_1, \ldots, a_{n-1}, $x$

$l = 0$ l=0;

$r = n$ r=n;

while ( $l < r - 1$ l < r - 1) {

$m = (l + r) /2$ m = (l + r) / 2;

if ( $a_{m} \leq x$ a_m \leq x)

$l = m$ l = m;

else

$r = m$ r = m;

}

if ( $a_{l} == x$ a_l == x)

return true;

else

return false;

Bəzən məlum olur ki, ikitərəfli axtarış, massiv sıralanmasa belə, bəzi elementlərin daxilolmalarını tapır. Sizə $n$ ədədi verilir. $a$ uzunluğu $n$ olan və $1$ ilə $n$ arasında tam ədədlərdən ibarət olan massivləri, $x$ isə $1$ ilə $n$ arasında tam ədəd olan cütlərin sayını tapmaq lazımdır ki, verilmiş prosedur $a$ massivində və $x$ ədədində işə salındıqda true qaytarsın.

Giriş

Giriş faylı bir tam ədəd $n$ ( $1 \leq n \leq 1000$ 1 \leq n \leq 1000) ehtiva edir.

Çıxış

Verilən məsələnin cavabı olan bir tam ədəd çıxarın.

Nümunələr

Nümunə 1

Loading

a_{0}, a_{1}, \dots, a_{n - 1}

l = 0

r = n

l < r - 1

m = (l + r) /2

a_{m} \leq x

l = m

r = m

a_{l} == x

1 \leq n \leq 1000