Напишите версию функции с одной проверкой внутри цикла - C (СИ)
Формулировка задачи:
Керниган и Ритчи "Язык программирования C". Упражнение 3.1
В этом двоичном поиске каждый цикл содержит две проверки, тогда как достаточно было бы одной (зато взамен их потребовалось бы больше снаружи цикла). Напишите версию функции с одной проверкой внутри цикла.
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; }
Решение задачи: «Напишите версию функции с одной проверкой внутри цикла»
textual
Листинг программы
int binsearch (int x, int v[], int n){ int low, high, mid; for( low = 0, high = n-1, mid = (low+high)/2; ( v[mid]!=x ) && ( low < high ); mid = (low+high)/2 ) { if (x < v[mid]){ high = mid - 1; }else{ low = mid +1; } } return mid; } int main(){ int nArr[] = {0,1,2,3,4,5,6,7,8,9}, i; printf( "%d\n", binsearch( 5, nArr, sizeof(nArr)/sizeof(int) ) ); return 0; }
Объяснение кода листинга программы
- В функции
binsearch
объявлены три переменные типаint
:low
,high
иmid
. Значение переменнойmid
инициализируется в первой итерации цикла. - Далее в цикле, пока условие
( v[mid]!=x ) && ( low < high )
истинно, выполняется следующая часть кода: - Если
x
меньше значения в индексеmid
в массивеv
, то значение переменнойhigh
уменьшается на единицу, чтобы в следующем шаге уменьшить область поиска. - Если
x
больше или равно значению в индексеmid
, то значение переменнойlow
увеличивается на единицу, чтобы в следующем шаге увеличить область поиска. - После каждой итерации значение переменной
mid
обновляется в соответствии с формулой(low+high)/2
. - Когда условие
( v[mid]!=x ) && ( low < high )
становится ложным, выполняется последняя часть кода внутри цикла: - Значение переменной
mid
возвращается из функции как результат. - В функции
main
объявлен массивnArr
типаint
с десятью элементами от 0 до 9. - Функция
binsearch
вызывается с аргументами 5, nArr иsizeof(nArr)/sizeof(int)
. - Результат работы функции
binsearch
выводится на экран с помощью функцииprintf
. - Функция
main
возвращает 0, чтобы указать, что программа успешно завершилась.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д