Форум русскоязычного сообщества Ubuntu


За новостями русскоязычного сообщества и Ubuntu в целом можно следить на нашей страничке в Google+

Автор Тема: Проблема с бинарным поиском, K&R  (Прочитано 196 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Jack Sparrow

  • Автор темы
  • Активист
  • *
  • Сообщений: 613
    • Просмотр профиля
Проблема с бинарным поиском, K&R
« : 20 Декабрь 2017, 12:54:47 »
K&R приводит программу для бинарного поиска и предлагает улучшить ее и сравнить результат. Прежде чем пробовать писать свою версию, попробовал сначала ту, что приводится в книге (раздел 3.3). В main написал свой код для проверки: создаю массив из 100 000 элементов, заполняю его числами от 0 до 99 999. Потом пробую найти индекс произвольного числа, например, 588. Все работает, но ... скучно, т.к. искомый индекс всегда совпадает с самим числом. Если число выходит из ранга, то возвращается -1, т.е. вроде бы все как нужно.
Пробую заполнить предварительно массив другими числами, например так (строка 10): arr[i] = i + 2 Запускаю, а программа зависает. Даже если перезапускаю терминал, то все равно глючит. Помогает лишь перезагрузка. Наверное, массивы и их индексация это тонкая материя, но пока не могу понять, в чем дело.
А вот вся программа:
#include <stdio.h>
/* binsearch: find x in v[0] <= v[0] <= ... <= v[n-1]; K&R version */
int binsearch (int, int [], int);


int main() {


    int i;
    int arr[100000];
    for (i = 0; i < 100000; i++)
        arr[i] = i;
   
    printf("%d\n", binsearch(588, arr, 100000-1));
    return 0;
}


/* binsearch */
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    /* found match */
            return mid;
    }
    return -1;    /* no match */
}
« Последнее редактирование: 20 Декабрь 2017, 21:56:48 от Jack Sparrow »
Если проблему можно решить за деньги, то это не проблема, а затраты. (с) Еврейская мудрость.

Оффлайн EvangelionDeath

  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 2349
  • Ubuntu Mate 16.04 х64
    • Просмотр профиля
Re: Проблема с бинарным поиском, K&R
« Ответ #1 : 20 Декабрь 2017, 15:18:38 »
Jack Sparrow, так или вы неправильно пример переписали, или он там неправильно записан
Код: C++
  1.     while (low <= high) {
  2.         mid = (low + high)/2;
  3.         if (x < v[mid])
  4.             high = mid - 1;
  5.         else if (x > v[mid])
  6.             low = mid + 1;
  7.         else    /* found match */
  8.             return mid;
  9.     }
  10.  
Fujitsu UH552: Intel Core i3-3217U, 16GB DDR3 1600MHz, Intel HD4000, Intel 535 120GB/Ubuntu 16.04 Mate
HP 625: AMD Athlon P320, 4GB DDR3 1333MHz, AMD HD4250, Seagate Momentus/Ubuntu 14.04 Mate

Оффлайн Jack Sparrow

  • Автор темы
  • Активист
  • *
  • Сообщений: 613
    • Просмотр профиля
Re: Проблема с бинарным поиском, K&R
« Ответ #2 : 20 Декабрь 2017, 20:25:29 »
Точно! Но ошибка, все же, в книге. Спасибо, все работает.
Если проблему можно решить за деньги, то это не проблема, а затраты. (с) Еврейская мудрость.

 

Страница сгенерирована за 0.172 секунд. Запросов: 24.