How to implement m-block search in an array in C? I rummaged through a half-runet and found only a brief description, and then it’s the same everywhere.

  • one
    Incomprehensible question. How should I understand, "implement for me" or "explain the algorithm"? Please specify what is unclear. Otherwise, the answer suggests itself: open a text editor and write code in C - yapycoder
  • An example of an M-block search in C. How does it work? - Endru

1 answer 1

I agree with the author, some kind of horror, they all copy the text from the books "Gromov Y. Yu., Tatarenko S. I. Programming in the SI language" and consider this an answer to the question =)

Here is the algorithm from my home library =)

/* M-блочный поиск. Предполагается, что исходный упорядоченный (отсортированный) массив B длины N разбит на M подмассивов B1, B2, ..., BM длин N1, N2, ..., NM, таким образом, что B={ B1, B2 , .., BM}. Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M, последний элемент которого больше V, а потом применить последовательный поиск к списку Bi. */ #include<stdio.h> void main() { int i, a[100], b[100], j, s = 0, k, x, z; int t; for (i = 0; i < 100; i++) a[i] = 0, b[i] = 0; // Ввод массива (упорядоченного!) for (i = 0;; i++) { printf("Enter A:"); scanf("%d", &a[i]); if (a[i] == -1) break; } // Ввод длинн подмассивов for (j = 0;; j++) { printf("Enter LEN"); scanf("%d", &b[j]); if ((s += b[j]) >= i) break; } printf("Find:"); scanf("%d", &x); j = 0; // printf("%d %d %d\n", k, a[k], b[j-1]); for (k = b[j++] - 1; (a[k] < x) && (k <= i); k += b[j++]) ; if (k > i) { printf("Error"); return; } for (z = k - b[j - 1]; (z <= k); z++) { if (a[z] == x) { printf("Number:%d\n", z); break; } } if (z >= k) printf("Not found\n"); } 
  • Perfectly! Thank you friend for help !!! - Endru