Алгоритмы поиска

Tartiblangan massivda ikkilik qidiruv

int binary_search(const struct KeyData A[], int N, K key) { int L = 0, R = N-1; do { int M = (L+R)/2; if (key == A[M].key) return M; if (A[M].key < key) L = M + 1; else R = M - 1; } while (L <= R); return -1; }

Tartiblangan massivda ikkilik qidiruv

4
10
17
19
20
28
25
2
33
45
40
42
39
35
46
64
71
77
85
89
99
X = 33
[
]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Qator osti qidiruvi

abcdaaccbbssacbaszzzaaa
cbbss
s
q

• N elementli s qator (matn) va M <= N elementli q qator berilgan (namuna)
• Matndagi q qolipining birinchi marta paydo bo‘lishi boshlanishini ko‘rsatuvchi k indeksini topish talab qilinadi s q[0] = s[k], q[1] = s[k+1], ..., q. [M−1] = s[ k+M − 1]

Sodda (to'g'ridan-to'g'ri) qator osti qidirish

• 1-qadam
• Namunaning chap chetini matnning chap chetiga "qo'llang", K = 0
• 2-qadam
• Q[j] naqsh belgilarini s[K+j] matn belgilarini chapdan o'ngga ketma-ket taqqoslash orqali naqshning matnga K-o'rindan boshlab kiritilganligini tekshiramiz.
• 3-qadam
• Agar bizda M mos kelsa, u holda matndagi namuna topiladi - ishning oxiri
• Agar K+M >= N bo'lsa, unda namuna topilmaydi - ishning oxiri
• Aks holda K = K+1 va 2-bosqichga o'ting
• Eng yomon holat O((N - M)*M) taqqoslashlari

To'g'ridan-to'g'ri pastki qator qidirish

int naive_substring_search(

const char s[], int N, const char q[], int M) { int k; // Matndan namuna ko`chirish for (k = 0; k < N-M; ++k) { int j; // Namuna ko`chirish for (j = 0; s[k+j]==q[j]; ++j) if (j == M-1) return k; // topildi } return -1; // Topilmadi }

Rabin-Karp algoritmi

• Maykl Rabin b. 1932 yil
• Karp, Richard M. Rabin, Maykl O. Samarali tasodifiy shablonga mos keladigan algoritmlar // IBM Journal of Research and Development Vol. 31(2), bet. 249-260, 1987 yil mart
• Richard Karp b. 1935 yil