2-маъруза. Булев излаш тизими функциялари

7-маъруза. Ахборотни излаш тизимларини моделлаштириш усуллари

Sortirovka qilinmagan massivda yozuvni eng oddiy qidirish butun ro'yxatni bosib o'tishga to'g'ri keladi

yozuv topilishidan oldin. Ushbu algoritm har doim ham samarali emas, lekin u o'zboshimchalik bilan ro'yxatda ishlaydi.

barchaning oddiy ketma-ket ko'rinishini tashkil etadi

massiv elementlari va mos yozuvlar bilan taqqoslash (kalit) X. Ushbu protsedura massivning topilgan elementi uchun indeks qiymatini yoki kerakli element topilmaganda nolni qaytaradi. To'g'ridan-to'g'ri ketma-ket qidirishda o'rtacha n 2 ta element tekshiriladi. Eng yaxshi holatda

ish bitta elementni tekshiradi, eng yomon holatda - n element. Agar ma'lumotlar saralanmagan bo'lsa,

keyin chiziqli qidirish mumkin bo'lgan yagona narsa.

Saralangan massivda klassik qidirish usullari: a) ikkilik qidirish; b) qidirish

"Fibonachchi daraxti"; v) interpolyatsion qidiruv.

Ikkilik qidiruv [7, 8, 9, 17] mos yozuvlar (kalit) ni massivning o'rtasidagi element bilan taqqoslaydi va

taqqoslash natijasiga (ko'p yoki oz) qarab, keyingi qidiruv chap tomonda amalga oshiriladi

yoki qatorning o'ng yarmida:

L: = 0; R: = N; f: = noto'g'ri; takrorlang m: = (L + R) div 2;

Agar a [m] = x bo'lsa f: = rost; Agar a [m]

Writeln (m, L, R); (L> = R) yoki (f) gacha;

Agar f bo'lsa, yozing ("element topildi", m, "joy") boshqasi

write (‘massivda bunday element yo‘q’);

Masalan, qatorni qidirish (1, 5, 12, 17, 21, 25, 32, 42, 45, 47, 51, 54, 57, 65, 78, 94)

quyidagicha tasvirlanishi mumkin.

1 2 7 1 5 2 2 5 7

besh

1 4 7 5 8 4]

2 7 1 5 2 2 45 7

besh

1 4 7 5 8 4]

2 7 1 5 2 2 45 7

besh

1] 4 7 5 8 4

2 7 1 5 2 2 5 7

[

51] 4 7 5 8 4

Avval o'rta element tekshiriladi, bu 42 raqami. Ushbu element

51 dan kam bo'lsa, qidiruv qatorning ikkinchi yarmida (45, 47, 51, 54, 57, 65, 78, 94) davom etadi, aks holda birinchi yarmi tekshiriladi. Jarayon qidirilgan element topilmaguncha davom etadi. Taqqoslashlar soni eng yomoni logn, eng yaxshisi 1. Algoritm ikkilik daraxt bilan ifodalanadi [7]: