Binar qidiruv algoritmi. Binar qidiruv daraxti. Prioritetli navbat. Binar qidiruv algoritmi

Binar qidiruv algoritmi. Binar qidiruv daraxti. Prioritetli navbat.

Binar qidiruv algoritmi.

Qidiruv algoritmlari ichida ko`p ishlatiladigani chiziqli qidiruv algoritmlari.

Chiziqli qidiruv algoritmining kamchiligi agar so`rovlar soni m ta bo`lsa va har bir so`rov uchun n ta amal bajarsa taqqoslashlar soni n*m bo`ladi. Agar n va m larning qiymatlari n=m=105 ko`rinishida bo`lsa, u holda 1010 amal talab qilinadi. Buni esa EXM qisqa vaqt ichida bajara olmaydi.

Binar qidiruv algoritmi.

Binar qidiruv algoritmi biror berilgan sonni saralangan massivdan qidirish(bor yoki yo`qligini aniqlash) imkon beradi.

Binar qidiruv algoritmida har bir amalda izlanayotgan interval 2 marta kamayadi, demak k ta amaldan keyin 2k marta kamayadi. Massiv elementlari soni n ta bo`lsa 2k = n => k=log2(n) yani n ta elementli massivdan izlash log2(n) ta amal bajaradi.

Binar qidiruv algoritmini amalga oshirishda hamisha quyidagi sonlar mavjud.

• Binar qidiruv algoritmini amalga oshirishda hamisha quyidagi sonlar mavjud.
• L(left, chap) – izlanayotgan intervalning chap indeksi chegarasi.
• R(right, o`ng) – izlanayotgan intervalning o`ng indeksi chegarasi.
• M – izlanayotgan intervalning o`rtadagi element indeksi.
• X = 32 – qidirilayotgan son.

4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11
L = 1, R = 12, m = (L+R)/2 = 6

O`rtadagi element 25 ga teng, 32≥25 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 6, R = 12, M = 9

O`rtadagi element 25 ga teng, 32≥25 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 6, R = 12, M = 9

4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11
4
7
10
14
18
25
28
32
37
41
46