Пример. Двоичный поиск в массиве.Пусть  элементы  массива  A  уже  расставлены  по  возрастанию  и  требуется  найти  элемент, равный  x,  среди  элементов  с  номерами  от  L  до  R..  Для  этого  используют  следующую  идею: выбираем  средний  элемент  между  L  и   R   ,   он   имеет   номер   m=(L+R)/2,   где   деление выполняется  нацело.  Сравним  его  с  искомым  x.  Если  он  равен  x,  поиск  завершен.  Если  x меньше элемента с номером, надо искать дальше между L и m, если больше m, дальше m и R. Обратите внимание, что элемент A[R] не рассматривается.

Решение.

#include <stdio.h>

const N = 10;

void main()

{

int L = 0, R = N, m, A[N], flag = 0;

// ввод массива A

printf("Введите искомый элемент\n”);

scanf( ”%d”, x );

while ( L < R ) {

   m = (L + R) / 2;

   if ( A[m] == x ) {

      flag = 1;

   break;

      }

if ( x < A[m] ) R = m;

   else            L = m + 1;

}

if ( flag )

     printf ( "Индекс нужного элемента %d", m );

else printf ( "Такого элемента нет” );

}


Оценка - 1.0 (19)
2009-12-19 • Просмотров [ 7222 ]