Лекция 2 Алгоритмы сортировки и поиска

Saralash va qidirish algoritmlari

Qidiruv algoritmini yanada yaxshilash mumkinmi?

Umuman- yo'q, shuning uchun eng yomon holatda biz D dan yaxshiroq vaqtga erisha olmaymiz (n).
YaxshilashBalki, faqat massivdagi elementlarning tartibi haqida biror narsa bilsak.
Faraz qilaylikmassiv kamaymaydigan tartibda tartiblanganligi, ya'ni. har bir massiv elementi “kichikroq” munosabatining ba’zi bir ta’rifiga ko‘ra, massivdagi o‘zidan keyingi elementdan kichik yoki unga teng:

• Raqamlar uchun, aniq
• Satrlar uchun leksikografik tartib.

Ikkilik qidiruv

Fikr: Har qanday vaqtda biz faqat pastki qatorni ko'rib chiqamiz, ya'ni. massivning ikkita indeks orasidagi qismi (shu jumladan). Keling, ularni p va r deb ataymiz va dastlab p = 1 va r =n. Ikki hodisadan biri sodir bo'lgunga qadar biz pastki qatorni qayta-qayta yarmiga bo'lamiz: yoki biz kerakli qiymatni topamiz, yoki pastki qator bo'sh (p > r).

• Faraz qilaylik, biz A massivda x qiymatini qidiramiz. Har bir qadamda faqat A[p] elementdan boshlanib, A[r] elementi bilan tugaydigan kichik massivni ko'rib chiqamiz - uni A[p..r] belgilaymiz. .
• Har bir qadamda biz pastki qatorning o'rta q ni hisoblaymiz, o'rtachani sifatida hisoblaymiz
• Agar A[q] = x, u holda kerakli element topiladi.
• Agar A[q] != x bo‘lsa, u holda…

Ikkilik qidiruv

1) A[q] > x holatida massivning tartiblanishi tufayli A[q] ning o'ng tomonida joylashgan barcha elementlar ham x dan katta. Keyingi bosqichda p o'zgarmaydi va r q-1 ga teng bo'ladi.
2) Agar A[q] < x bo'lsa, A[q] ning chap tomonidagi massivning har bir elementi x dan kichik bo'ladi va shuning uchun bu elementlarni e'tiborsiz qoldirish mumkin. Shuning uchun keyingi bosqichda r o'zgarmaydi va p q +1 ga teng bo'ladi.

Ikkilik qidiruv algoritmi