Преобразование в цикл

Инвариант: a_j > a₁ > … > a_i , a_j >= b >= a_i

Предусловие: i=n-1; j=0;

Тело цикла

t=целая часть[(i+j)/2];

если a_t < b i = t;

иначе j = t;

Постусловие i=j+1;

Пример программы:

// Находит в массиве mas размером n, упорядоченном по убыванию, элемент s

// Возвращает номер этого элемента в массиве, n если элемент на найден

int dsearsh(int *mas, int n, int s)

{

if(mas[0]<s) return n;

if(mas[n-1]>s) return n;

int i=n-1, j=0, t;

while(i!=j+1)

if(mas[t=(i+j)/2]<s) i=t;

else j=t;

if(mas[i]==s) return i;

if(mas[j]==s) return j;

return n;

}

main()

{

int a[]={18, 16, 14, 12, 10, 8, 6, 4, 2, 0};

int elem[]= {10, 11, 0, 18};

int ans[] = {4, 10, 9, 0};

int i, res, ntest=4, n=10;

printf("\nMassive:\n");

for(i=0; i<n; i++)

printf("%i ", a[i]);

printf("\n\n");

for(i=0; i<ntest; i++)

{

printf("Test %i\n", i);

printf("element - %i\n", elem[i]);

res=dsearsh(a, 10, elem[i]);

printf("a[%i]=%i\n", res, a[res]);

if(res==ans[i]) printf("test passed\n\n");

else printf("test failed\n\n");

}

}