Пример. Двоичный поиск в массиве.Пусть элементы
массива 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 ( "Такого элемента нет” );
}
2009-12-19 • Просмотров [ 7445 ]