5В060200 «Информатика» мамандығына арналған

Егер массив реттелмеген болса, онда біртіндеп іздеу әдісін қолдануға болады:

A[1..n] массиві берілсін. P-ға тең элементті іздеу керек болсын.

1. i=1; болғанда бастаймыз

2. егер a_i=p шарты орындалса, онда іздеу сәтті аяқталады

3. әйтпесе I:=i+1 деп келесі элементке көшеміз

4. егер i<=n болса, онда 2-ші пунктке көшеміз, әйтпесеәздеу сәтсіз аяқталады.

Бұл алгоритмнің күрделілігі n-1-ге тең, себебі элементтерді р-мен салыстыру саны сонша.

Егер массив реттелген болса, онда бинарлы-екілік іздеуді қолдануға болады. Оны логарифмдік іздеу немесе дихотомия әдісі дейді.

Мұнда екі көрсеткіш пайдаланады: l=1 массивтің алғашқы элементін көрсетеді, u=n массивтің соңғы элементін көретеді:

1. l=1; u=n; болады

2. егер ul<=k<=a_u шартының орындалатынын білеміз. I=(l+u) div 2 деп аламыз , сонда I массивтің ортасын көрсетеді.

3. Егер ki болса, онда 4-ші пунктке көшеді, егер k>a_i болса, онда 5-ші пунктке көшеді, егер k=a_i болса, онда іздеу сәтті аяқталады.

4. u=i-1 деп орналастырамыз және 2-ші пунктке көшеміз

5. l=i+1 деп орналастырамыз және 2-ші пунктке көшеміз.