K&R (71-72). Двоичный поиск

Опубликовано plustilino в Апрель 18, 2012 - 13:44. Changed Апрель 18, 2012 - 14:08

Решение задач на языке программирования C

В книге описана функции поиска элемента в упорядоченном массиве с помощью алгоритма двоичного поиска (дихотомии).

Пример рабочей программы с использованием этой функции:

#include <stdio.h>
 
int binsearch (int x, int v[], int n);
 
main () {
	int n = 10;
	int i, k = 2;
	int arr[n];
 
	for (i = 0; i < n; i++) {
		arr[i] = k;
		k += 3;
		printf ("%d ", arr[i]);
	}
 
	printf ("\n");
	scanf ("%i", &k);
 
	i = binsearch (k, arr, n);
	printf("%d\n", i);
}
 
int binsearch (int x, int v[], int n) {
	int low, high, mid;
 
	low = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (x < v[mid])
			high = mid - 1;
		else 
			if (x > v[mid])
				low = mid + 1;
			else
				return mid;
	}
	return -1;
}