Бинарлық іздеу алгоритмін сипаттаңыз

Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі:

1. Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2.

2. Орталық элементтің мәнін кілтпен салыстыру «Key». Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.

3. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.

Бинарлық қоюлар арқылы сұрыптау жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу қашан енгізу орыны анықталғанша жалғаса беретін бинарлық іздеу жүргізіледі.

Программасы:

#include <iostream.һ>

using namespace std;

const int N=10;

//екілік іздеу

int BinarySearch(int A[], int key)

{

int left=0, right=N, mid;

while (left<=right)

{

mid=left+(right-left)/2;

if (key<A[mid]) right=mid-1;

else if (key>A[mid]) left=mid+1;

else return mid;

}

return -1;

}

//басты функция

void main()

{

int i, key;

int A[N];

cout<<"Izdelip otyrgan element";

cin>>key; //ввод ключа

cout<<"Bastapky massiv: ";

for (i=0; i<N; i++) //массивті енгізу және шығару

{ A[i]=N*i; cout<<A[i]<<" "; }

if (BinarySearch(A, key)==-1) cout<<"\nElement tabylmady";

else cout<<"\nElement nomeri: "<<BinarySearch(A, key)+1;

system("pause>>void");

}