НачалоПодразделы
Другие разделы
| Занятие 1 |
| Занятие 2 |
| Занятие 3 |
| Занятие 4 |
| Занятие 6 |
| Занятие 7 |
| Занятие 8 |
| Занятие 9 |
| Занятие 10 |
| Занятие 11 |
| Занятие 12 |
| Занятие 13 |
| Занятие 14 |
| Занятие 15 |
| Занятие 16 |
| Занятие 17 |
| Занятие 18 |
| Занятие 19 |
| Занятие 20 |
Дата и время
16/11/2024 21:14:23
Занятие 5
Бинарный поиск
Задачу бинарного поиска сформулируем так. Есть функция-предикат `f`, принимающая на отрезке от `A` до `X` значение 0, а на отрезке от `X` до `B` значение 1. Найти значение `X`, т.е. минимальное значение `X`, для которого `f(X)=1`.
Рассмотрим значение функции `f` в середине отрезка `[A,B]`. В случае если оно равно 0, то можно отбросить левую половину отрезка, а в случае 1 – правую. Таким образом длина отрезка для поиска `X` уменьшается вдвое. В случае вещественного диапазона для поиска решения с точностью `ε` требуется `log_2\ ((B-A)/ε)` шагов. В случае дискретных значений для поиска потребуется `log_2(B-A+1)` шагов.
double bsrch(double a, double b, double eps, bool (*f)(double))
{ double c;
while(b-a>=eps)
{ c=(b+a)/2;
if(f(c)) b=c;
else a=c;
}
return b;
}
Для дискретного случая программа выглядит аналогично.
int bsrch(int a, int b, bool (*f)(int))
{ int c;
while(a<b)
{ c=(b+a)/2;
if(f(c)) b=c;
else a=c+1; // !!!
}
return b;
}
Пусть требуется найти индекс первого нулевого элемента в упорядоченном по возрастанию массиве.
int m[100]; // упорядоченный массив int n; // количество элементов int k; // индекс bool f0(int i) { return m[i]>=0; } ... k=bsrch(0,n,f0); // n, а не n-1, чтобы функция возвращала n, // если все элементы в массиве отрицательные if(k==n || m[k]!=0) printf("Нет элемента\n"); else printf("%d\n",k);
