Функция бинарного поиска в последовательности

@Abros · Регистрация: 19.10.2016

Author24 — интернет-сервис помощи студентам

Составьте функцию binsearch, выполняющую поиск заданного числа в последовательности чисел, отсортированном по возрастанию, методом деления пополам (см. http://lord-n.narod.ru/downloa... 1/2111.htm). Функция должна быть объявлена как

unsigned long binsearch(unsigned long nel, int (*compare)(unsigned long i))
{
...
}
Здесь параметр nel задаёт количество элементов в последовательности, а параметр compare – указатель на функцию сравнения, которая принимает параметр i и и возвращает:

-1, если i-тое число в последовательности меньше искомого числа;
0, если они равны;
1, если i-тое число больше искомого числа.
Функция binsearch должна возвращать индекс найденного элемента или значение nel, если такого элемента не существует.
Проверка работоспособности функции binsearch будет осуществляться путём присоединения её к программе вида

C

#include <stdio.h> 
 
int array[] = { 1, 2, 30, 45, 50, 51, 55, 60 }; 
const int k = 51; 
 
int compare(unsigned long i) 
{ 
        if (array[i] == k) return 0; 
        if (array[i] < k) return -1; 
        return 1; 
} 
 
unsigned long binsearch(unsigned long, int (*)(unsigned long)); 
 
int main(int argc, char **argv) 
{ 
        printf("%lu\n", binsearch(8, compare)); 
        return 0; 
}

	21.10.2016, 21:44

Опции темы