В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n<k=2m.
Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Т .к. массив упорядочен, то если a[S]<X, то искомый элемент находится в правой части массива, иначе - находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.
L S R
S=(L+R)/2=4
int b;
cout<<" B=?";cin>>b;
int l=0,r=n-1,s;
do
{
s=(l+r)/2;//средний элемент
if(a[s]<b)l=s+1;//перенести левую границу
else r=s;//перенести правую границу
}while(l!=r);
if(a[l]==b)return l;
else return -1;