Напишите версию функции с одной проверкой внутри цикла - 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; 
}

Объяснение кода листинга программы

  1. В функции binsearch объявлены три переменные типа int: low, high и mid. Значение переменной mid инициализируется в первой итерации цикла.
  2. Далее в цикле, пока условие ( v[mid]!=x ) && ( low < high ) истинно, выполняется следующая часть кода:
  3. Если x меньше значения в индексе mid в массиве v, то значение переменной high уменьшается на единицу, чтобы в следующем шаге уменьшить область поиска.
  4. Если x больше или равно значению в индексе mid, то значение переменной low увеличивается на единицу, чтобы в следующем шаге увеличить область поиска.
  5. После каждой итерации значение переменной mid обновляется в соответствии с формулой (low+high)/2.
  6. Когда условие ( v[mid]!=x ) && ( low < high ) становится ложным, выполняется последняя часть кода внутри цикла:
  7. Значение переменной mid возвращается из функции как результат.
  8. В функции main объявлен массив nArr типа int с десятью элементами от 0 до 9.
  9. Функция binsearch вызывается с аргументами 5, nArr и sizeof(nArr)/sizeof(int).
  10. Результат работы функции binsearch выводится на экран с помощью функции printf.
  11. Функция main возвращает 0, чтобы указать, что программа успешно завершилась.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 4.125 из 5
Похожие ответы