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

Protsedura BinarySearch(A,n,x).
kirish va chiqish: Linear-Search bilan bir xil.
Jarayon bosqichlari:
1. p ni 1 ga va r ni n ga o‘rnating.
2. p ≤ r bo‘lganda, quyidagilarni bajaring.
A. q ni o‘rnating
B. Agar A[q] = x, q ni qaytaring.
C. Aks holda (A[q] != x), agar A [q] > x,
r ni q-1 ga o‘rnating.
D. Aks holda (A[q] < x) p ga teng bo'ladi
q+1.
3. Topilmagan qiymatni qaytaring.
Loop invariant: “2-bosqichda siklning har bir iteratsiyasi boshida, agar x A massivning biror joyida bo‘lsa, bu qiymat A[p..r] kichik massiv elementlaridan birida bo‘ladi”.

Rekursiv ikkilik qidiruv

Rekursiv-ikkilik-qidiruv (A,p,r,x) protsedurasi.
kirish va chiqish: A va x kiritish parametrlari Chiziqli qidiruv protsedurasi bilan bir xil, shuningdek chiqish. Kirish parametrlari p va r qayta ishlangan kichik massiv A[r..r] ni belgilaydi.
Jarayon bosqichlari:
1. Agar p > r bo'lsa, topilmadi.
2. Aks holda (p < r), quyidagilarni bajaring.
A. O'rnatish
B. Agar A[q] = x, q ni qaytaring.
C. Aks holda (A[q] != x), agar A[q] > x bo‘lsa, qaytaring
Rekursiv-ikkilik-qidiruv(A,p,q-1,x).
D. Aks holda (A[q] < x) qaytariladi
Rekursiv-ikkilik-qidiruv(A,q+1,r,x).

Ikkilik qidiruv vaqti

• Asosiy fakt: ko'rib chiqilayotgan pastki qatorning o'lchami r-p+1 tsiklning har bir iteratsiyasida taxminan yarmiga kamayadi.
• Savol: ko'rib chiqilayotgan pastki qatorni yarmiga bo'lgan halqaning qancha takrorlanishi amalga oshirilishi kerak, shunda uning asl hajmi bo'ladi.n1 ga qisqartirildi?
• Javoboddiygina 2 ga ko'paytirish yo'li bilan kuchga ko'tarish bilan aniqlanadi. Agarn2 ning aniq kuchi bo'lsa, javob raqamlar jurnali bo'ladi2n. Agar yo'q bo'lsa, unda logdan farq2n1 dan ortiq emas.
• Ish vaqtihisoblanadiO(log2n) har bir iteratsiya uchun doimiy vaqt sarflanishini nazarda tutgan holda.
• Eng yomon holat(massivda x qiymati yo'q): D (log2n).
• eng yaxshi holat(x birinchi iteratsiyada topiladi): D(1).

Ikkilik qidiruv chiziqlidan tezroq [O(log2n)<O(n)], lekin massivni oldindan saralashni talab qiladi.