Упражнение 3.1.

В нашей программе бинарного поиска внутри цикла осуществляются две проверки, хотя могла быть только одна (при увеличении числа проверок вне цикла). Напишите программу, предусмотрев в ней одну проверку внутри цикла. Оцените разницу во времени выполнения.

$ vim binsearch.c

#include <stdio.h>

int binsearch(int x, int v[], int n);

int main(void)
{
    int index = 10;
    int arr[10] = { 1, 3, 4, 7, 15, 18, 33, 34, 67, 88 }; /* упорядоченный по возрастанию массив из 10 элементов */
    int pos;  /* позиция искомого значения в массиве */
    int el = 3;  /* искомое значение */

    pos = binsearch(el, arr, index);
    printf("Значение %d имеет индекс %d\n", el, pos);

    return 0;
}

/* binsearch: найти x в v[0] <= v[1] <= ... <= v[n-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;
        else
            low = mid + 1;
    }

    return (x == v[low]) ? low : -1;
}

$ cc -g -O0 -Wall -o a.out binsearch.c

$ ./a.out

Значение 3 имеет индекс 1

Для оценки разницы во времени выполнения придется немного модифицировать программу: увеличить размер массива и использовать функцию clock_t clock(void), которая возвращает время, измеряемое процессором в тактах от начала выполнения программы, или −1, если оно не известно. Пересчет этого времени в секунды будем выполнять по формуле:
clock() / CLOCKS_PER_SEC.
Функция clock()определена в заголовочном файле time.h стандартной библиотеки. Пример использования функции clock() я взял тут.

$ vim comparison.c

#include <stdio.h>
#include <time.h>

#define MAX 50000       /* размер массива */

int binsearch1(int x, int v[], int n);
int binsearch2(int x, int v[], int n);

int main(void)
{
    int i = 0;
    int index = 0;
    int arr[MAX];
    int pos;  /* позиция искомого значения в массиве */
    int el = 12345;  /* искомое значение */
    clock_t start, stop;        /* время начала и конца выполнения функции binsearch */

    /* Заполнение массива */
    for (index = 0; index < MAX; index++)
      arr[index] = index;

    /* начало выполнения  binsearch1 */
    start = clock();

    for (i = 0; i < 50000; i++)
        pos = binsearch1(el, arr, MAX);

    /* конец выполнения binsearch1 */

    stop = clock() - start;

    printf("binsearch1: значение %d имеет индекс %d\n", el, pos);
    printf("Время выполнения функции %f секунд\n", (float)stop / CLOCKS_PER_SEC);

    /* начало выполнения binsearch2*/
    start = clock();

    for (i = 0; i < 50000; i++)
        pos = binsearch2(el, arr, MAX);

    /* конец выполнения binsearch2 */
    stop = clock() - start;

    printf("binsearch2: значение %d имеет индекс %d\n", el, pos);
    printf("Время выполнения функции %f секунд\n", (float)stop / CLOCKS_PER_SEC);

    return 0;
}

/* binsearch1: найти y в w[0] <= w[1] <= ... <= w[m-1] */
int binsearch1(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;
}

/* binsearch2: найти x в v[0] <= v[1] <= ... <= v[n-1] */
int binsearch2(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;
        else
            low = mid + 1;
    }
    return (x == v[low]) ? low : -1;

}

$ cc -g -O0 -Wall -o a.out comparison.c

$ ./a.out

binsearch1: значение 12345 имеет индекс 12345
Время выполнения функции 0.010000 секунд
binsearch2: значение 12345 имеет индекс 12345
Время выполнения функции 0.030000 секунд

$ ./a.out

binsearch1: значение 12345 имеет индекс 12345
Время выполнения функции 0.020000 секунд
binsearch2: значение 12345 имеет индекс 12345
Время выполнения функции 0.030000 секунд

$ ./a.out

binsearch1: значение 12345 имеет индекс 12345
Время выполнения функции 0.020000 секунд
binsearch2: значение 12345 имеет индекс 12345
Время выполнения функции 0.040000 секунд

Вывод: Функция, предложенная авторами книги выполняется быстрее.