Поиск в отсортированном массиве

Сортировка методом простого обмена

Сравниваются и меняются местами пары элементов, начиная с последнего (или с первого). В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива, пока не будут упорядочены все элементы. Определить, что элементы упорядочены, можно по количеству выполненных перестановок N: если N=0, то массив отсортирован.

				94

for(int i=1;i<n;i++)

for(int j=n-1;j>=i;j--)

if(a[j]<a[j-1])

{

int r=a[j];

a[j]=a[j-1];

a[j-1]=r;}

}

В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n<k=2^m.

Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то, если a[S]<X – искомый элемент находится в правой части массива, иначе – находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.

L S R

int b;

cout<<"\nB=?";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;

…