fbpx
Wikipedia

İkili axtarış alqoritmi

Avqust 18, 2021

İ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

Geyd 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. Məsəl üçü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ğyndur. 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)) {  int sol = 0;  int sag = 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

Avqust 18, 2021
ikili, axtarış, alqoritmi, ikilik, binar, yarıya, bölməklə, axtarış, 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, axtarış, aparmağa. Ikilik Binar ve ya yariya bolmekle axtaris ing Binary search Siralanmis massivde mueyyen qiymetin axtarilmasi alqoritmidir Xetti axtarisdan ferqli olaraq Binar axtaris siralanmis massivler uzerinde daha tez axtaris aparmaga imkan verir Xususile boyuk hecmli verilenler bazasina sahib proqramlarda xetti axtaris texniki olaraq cox vaxt teleb etdiyinden yaramir Mundericat 1 Isleme prinsipi 2 Numune 3 C proqramlasdirma dilinde tesviri 4 Elave telebler 5 Hemcinin baxIsleme prinsipi RedakteAlqorimtin islemesi ucun ilk once massiv siralanmis olmalidir Bu usul ile axtaris zamani axtarilan melumat massivin ortadaki elementi ile muqayise edilir Eger axtarilan eded ortadaki elementden boyukdurse o zaman hemin ededden kicik hisseler unudulur ve axtaris boyuk olan hissede aparilir ve ya eksine Her bele muqayisede axtaris yariya endirilir Numune Redaktea axtarilan eded M massiva 4 M 1 3 4 6 8 9 11a ile 6 i muqayise et Kicikdir Axtarisi M 1 3 4 ile apar a ile 3 u muqayise et Boyukdur Axtarisi M 4 ile apar a ile 4 u muqayise et Beraberdir Axtaris tamamlandi a tapildi C proqramlasdirma dilinde tesviri Redakte include lt stdlib h gt srand rand RAND MAX include lt stdio h gt printf scanf include lt time h gt time include lt locale h gt setlocale define FALSE 0 define TRUE 1 define n 12 Massivin olcusu Artan sira ile duzulmus massivde ikilik axtaris funksiyasina numune int YariYariyaAxtarma int massiv int say int axtarilan Trivial hallari ele yerindece cavablandira bilerik if massiv 0 gt axtarilan massiv say 1 lt axtarilan return 1 int bas 0 int son say 1 while bas lt son int orta bas son 2 if massiv orta axtarilan return orta if massiv orta gt axtarilan son orta 1 else bas orta 1 return 1 Massivi siralamaq ucun teleb olunan muqaise funksiyasi Bu funksiya massivi artan sira ile duzur int compare const void elem1 const void elem2 if int elem1 gt int elem2 return 1 if int elem1 lt int elem2 return 1 return 0 Alqoritminin istifadesine numune int main int massiv n int i setlocale LC ALL utf8 srand unsigned time NULL printf Massivdeki ededlerin ilkin tesadufi sirasi t for i 0 i lt n i massiv i 100 0 rand RAND MAX 1 printf d massiv i printf n ikilik axtaris ucun massivin axtarisin istiqametinden asili olaraq siralanmasi mutleqdir qsort massiv n sizeof int compare printf Massivdeki ededler siralandiqdan sonra t t for i 0 i lt n i printf d massiv i printf n while TRUE int axtarilan printf n Proqramdan cixmaq ucun menfi sirasinin tapilmasi ucun ise her hansi bir diger eded daxil edin scanf d amp axtarilan if axtarilan lt 0 break int cavab YariYariyaAxtarma massiv n axtarilan if cavab lt 0 printf Cavab tapilmadi n else printf Sira N d n cavab 1 Elave telebler RedakteGeyd etmek lazimdir ki burda verilen numune numayis xarakteri dasiyir Praktiki meselelerin helli ucun alqoritme elave telebler ireli surule biler Mesel ucun siralama alqoritminde istifade edilmesi ucun alqoritmin elementin massivdeki yerini deyil onun elave edilmesi ucun en uygun olan yeri qaytarmasi meqsede uygyndur Bu ise artan sira ile duzdukde mumkun olan en sag veziyyet azalan sira ile duzdukde ise en sol veziyyetdir Bunu tam ededler massivini artan sira ile duzen siralama alqoritminin numunesinde gosterek include lt stdlib h gt srand rand RAND MAX include lt stdio h gt printf include lt conio h gt getch include lt memory h gt memcpy include lt time h gt time include lt locale h gt setlocale define n 12 Elementlerin sayi Artan sira ile duzulmus massivde yariya bolme ile axtarisin heyata kecirilmesi int YariYariyaAxtarma int massiv const int say const int axtarilan int compare const int const int int sol 0 int sag say while sol lt sag int orta sol sag sol 2 if compare massiv orta axtarilan gt 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 lt say i int elem massiv i Novbeti elementi gotururuk if compare elem massiv i 1 gt 0 continue ne ise etmeye ehtiyac yoxdur int yeniYer YariYariyaAxtarma massiv i elem compare elementin massivdeki yeni yerini tapiriq memcpy massiv yeniYer 1 massiv yeniYer i yeniYer sizeof int hemin yeri bosaldiriq massiv yeniYer elem elementi yeni tapdigimiz yere yerlesdiririk Massivi artan sira ile duzmek ucun teleb olunan muqaise funksiyasi int Compare const int elem1 const int elem2 if elem1 gt elem2 return 1 if elem1 lt elem2 return 1 return 0 Alqoritminin istifadesine numune int main int massiv n int i setlocale LC ALL utf8 srand unsigned time NULL printf Massivdeki ededlerin ilkin tesadufi sirasi t for i 0 i lt n i massiv i 100 0 rand RAND MAX 1 printf d massiv i printf n MakeSort massiv n Compare massivin artan sira ile duzulmesi printf Massivdeki ededler sira ile duzuldukden sonra t for i 0 i lt n i printf d massiv i printf n getch Hemcinin bax RedakteAxtaris alqoritmleri Diger proqramlasdirma dillerinde tesviriMenbe https az wikipedia org w index php title Ikili axtaris alqoritmi amp oldid 5538318, wikipedia, oxu, kitab, kitabxana, axtar, tap, hersey,

ne axtarsan burda

, en yaxsi meqale sayti, meqaleler, kitablar, oyrenmek, wiki, bilgi, tarix, seks, porno, indir, yukle, sex, azeri sex, azeri, seks yukle, sex yukle, izle, seks izle, porno izle, mobil seks, telefon ucun, chat, azeri chat, tanisliq, tanishliq, azeri tanishliq, sayt, medeni, medeni saytlar, chatlar, mekan, tanisliq mekani, mekanlari, yüklə, pulsuz, pulsuz yüklə, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, şəkil, muisiqi, mahnı, kino, film, kitab, oyun, oyunlar.