İkili axtarış alqoritmi

İkilik (Binar) və ya yarıya bölməklə axtarış (ing. Binary search) — Sıralanmış massivdə müəyyən qiymətin axtarılması alqoritmidir. Xətti axtarışdan fərqli olaraq Binar axtarış sıralanmış massivlər üzərində daha tez axtarış aparmağa imkan verir. Xüsusilə böyük həcmli verilənlər bazasına sahib proqramlarda xətti axtarış texniki olaraq çox vaxt tələb etdiyindən yaramır.

İşləmə prinsipi

Alqorimtin işləməsi üçün ilk öncə massiv sıralanmış olmalıdır. Bu üsul ilə axtarış zamanı axtarılan məlumat massivin ortadakı elementi ilə müqayisə edilir. Əgər axtarılan ədəd ortadakı elementdən böyükdürsə o zaman, həmin ədəddən kiçik hissələr unudulur və axtarış böyük olan hissədə aparılır və ya əksinə. Hər belə müqayisədə axtarış yarıya endirilir.

Nümunə

a = axtarılan ədəd, M = massiv

a = 4, M = 1 3 4 6 8 9 11

a ilə 6-ı müqayisə et. Kiçikdir. Axtarışı M = 1 3 4 ilə apar.

a ilə 3-ü müqayisə et. Böyükdür. Axtarışı M = 4 ilə apar.

a ilə 4-ü müqayisə et. Bərabərdir. Axtarış tamamlandı, a tapıldı.

C proqramlaşdırma dilində təsviri

#include <stdlib.h>/*srand(), rand(), RAND_MAX*/ #include <stdio.h>/*printf(), scanf()*/ #include <time.h>/*time()*/ #include <locale.h>/*setlocale()*/  #define FALSE 0 #define TRUE 1  #define n 12/* Massivin ölçüsü */  /* Artan sıra ilə düzülmüş massivdə ikilik axtarış funksiyasına nümunə */ int YariYariyaAxtarma(int massiv[], int say, int axtarilan) { /* Trivial halları elə yerindəcə cavablandıra bilərik */ //if (massiv[0] > axtarilan || massiv[say - 1] < axtarilan) //return -1;  int bas = 0; int son = say - 1;  while (bas <= son) { int orta = (bas + son) / 2;  if (massiv[orta] == axtarilan) return orta;  if (massiv[orta] > axtarilan) son = orta - 1; else bas = orta + 1; }  return -1; }  /* Massivi sıralamaq üçün tələb olunan müqaisə funksiyası.*/ /* Bu funksiya massivi artan sıra ilə düzür.*/ int compare(const void* elem1, const void* elem2) { if (*((int*)elem1) > *((int*)elem2)) return 1;  if (*((int*)elem1) < *((int*)elem2)) return -1;  return 0; }  /* Alqoritminin istifadəsinə nümunə */ int main() { int massiv[n]; int i;  setlocale(LC_ALL, ".utf8"); srand((unsigned)time(NULL));  printf("Massivdəki ədədlərin ilkin təsadüfi sırası:\t"); for (i = 0; i < n; i++) { massiv[i] = 100.0 * rand() / (RAND_MAX + 1); printf("%d ", massiv[i]); } printf("\n");  /* ikilik axtarış üçün massivin, axtarışın istiqamətindən asılı olaraq sıralanması mütləqdir */ qsort(massiv, n, sizeof(int), compare);  printf("Massivdəki ədədlər sıralandıqdan sonra:\t\t"); for (i = 0; i < n; i++) printf("%d ", massiv[i]); printf("\n");  while (TRUE) { int axtarilan;  printf("\nProqramdan çıxmaq üçün mənfi, sırasının tapilması üçün isə hər hansı bir digər ədəd daxil edin: "); scanf("%d", &axtarilan);  if (axtarilan < 0) break;  int cavab = YariYariyaAxtarma(massiv, n, axtarilan);  if (cavab < 0) printf("Cavab tapilmadi.\n"); else printf("Sıra N=: %d.\n", cavab + 1); } } 

Əlavə tələblər

Qeyd etmək lazımdır ki, burda verilən nümunə nümayiş xarakteri daşıyır. Praktiki məsələlərin həlli üçün alqoritmə əlavə tələblər irəli sürülə bilər. Misalçün, sıralama alqoritmində istifadə edilməsi üçün alqoritmin elementin massivdəki yerini deyil, onun əlavə edilməsi üçün ən uyğun olan yeri qaytarması məqsədə uyğundur. Bu isə artan sıra ilə düzdükdə mümkün olan ən sağ vəziyyət, azalan sıra ilə düzdükdə isə ən sol vəziyyətdir. Bunu tam ədədlər massivini artan sıra ilə düzən sıralama alqoritminin nümunəsində göstərək:

#include <stdlib.h>/*srand(), rand(), RAND_MAX*/ #include <stdio.h>/*printf()*/ #include <conio.h>/*_getch()*/ #include <memory.h>/*memcpy()*/ #include <time.h>/*time()*/ #include <locale.h>/*setlocale()*/  #define n 12/* Elementlərin sayı */  /* Artan sıra ilə düzülmüş massivdə yarıya bölmə ilə axtarışın həyata keçirilməsi */ int YariYariyaAxtarma(int massiv[], const int say, const int axtarilan, int(*compare)(const int, const int)) { intsol = 0; intsag = say;  while (sol < sag) { int orta = sol + (sag - sol) / 2;  if (compare(massiv[orta], axtarilan) > 0) sag = orta; else sol = orta + 1; }  return sag; }  void MakeSort(int massiv[], const int say, int(*compare)(const int, const int)) { for (int i = 1; i < say; i++) { int elem = massiv[i];/* Növbəti elementi götürürük */  if (compare(elem, massiv[i - 1]) > 0) continue;/* nə isə etməyə ehtiyac yoxdur */  int yeniYer = YariYariyaAxtarma(massiv, i, elem, compare);/* elementin massivdəki yeni yerini tapırıq */  memcpy(massiv + yeniYer + 1, massiv + yeniYer, (i - yeniYer) * sizeof(int));/* həmin yeri boşaldırıq */  massiv[yeniYer] = elem;/* elementi yeni tapdığımız yerə yerləşdiririk */ } }  /* Massivi artan sıra ilə düzmək üçün tələb olunan müqaisə funksiyası.*/ int Compare(const int elem1, const int elem2) { if (elem1 > elem2) return 1;  if (elem1 < elem2) return -1;  return 0; }  /* Alqoritminin istifadəsinə nümunə */ int main() { int massiv[n]; int i;  setlocale(LC_ALL, ".utf8"); srand((unsigned)time(NULL));  printf("Massivdəki ədədlərin ilkin təsadüfi sırası:\t"); for (i = 0; i < n; i++) { massiv[i] = 100.0 * rand() / (RAND_MAX + 1); printf("%d ", massiv[i]); } printf("\n");  MakeSort(massiv, n, Compare);/* massivin artan sıra ilə düzülməsi */  printf("Massivdəki ədədlər sıra ilə düzüldükdən sonra:\t"); for (i = 0; i < n; i++) printf("%d ", massiv[i]); printf("\n");  _getch(); } 

Həmçinin bax

• Axtarış alqoritmləri
• Digər proqramlaşdırma dillərində təsviri