K&R exercise 3.1 - C (СИ)

Формулировка задачи:

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

/* binsearch: найти х в 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 - 1;
else if (x > v[mid])
low = mid + 1 ;
else /* совпадение найдено */
return mid;
}
return -1; /* совпадения нет */
}

Как решить не знаю. Как оценить разницу во времени выполнения, если в пройденном материале нет инфы по работе со временем и датой? С помощью IDE какой-то может быть, которая выводит время выполнения программы, не знаю. Использую Pelles C.

Решение задачи: «K&R exercise 3.1»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
#include  <inttypes.h>
#include  <x86intrin.h>
#define N 200
 
int main()
{
 
    time_t start, stop;
    int i, x = (N+N/10)/2, n = N - N/10, b1, b2, b3;
    int a[N];
    for (i=0; i < N; i++)
    {
        a[i] = i + 9;
        printf("%d ", a[i]);
    }
 
    printf("\nArray length: %d (x=%d, n=%d)\n", N, x, n);
 
    uint64_t t;
    t = __rdtsc();
    b1 = binsearch(x, a, n);
    t = __rdtsc()-t;
    printf("binsearch:  ticks: %" PRIu64 "\n",t);
    printf("Position of element: %d\n", b1);
 
    t = __rdtsc();
    b2 = binsearch2(x, a, n);
    t = __rdtsc()-t;
    printf("binsearch2:  ticks: %" PRIu64 "\n",t);
    printf("Position of element: %d\n", b2);
 
    t = __rdtsc();
    b3 = binsearch3(x, a, n);
    t = __rdtsc()-t;
    printf("binsearch3:  ticks: %" PRIu64 "\n",t);
    printf("Position of element: %d\n", b3);
 
    return 0;
}
 
int binsearch (int x, int a[], int n)
{
    int l = 0, h = n, m;
    while (l < h)
    {
        m = (l+h)/2;
        if (x <= a[m])
            h = m;
        else
            l = m+1;
    }
    if (h<n && a[l] == x) return l;
    return -1;
}
 
int binsearch2 (int x, int a[], int n)
{
    int l=0, h=n, m;
    while (l <= h)
    {
        m = (l+h)/2;
        if (x < a[m])
            h = m - 1;
        else if(x > a[m])
            l = m + 1;
        else
            return m;
    }
    return -1;
}
 
int binsearch3 (int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    mid = (low+high)/2;
    while (low <= high && x != v[mid])
    {
        if (x < v[mid])
            high = mid - 1;
        else
            low = mid + 1;
        mid = (low+high)/2;
    }
    if (x == v[mid])
        return mid;
    else
        return -1;
}

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

Включаются необходимые заголовочные файлы
Объявляются переменные: time_t start, stop; int i, x, n, b1, b2, b3; uint64_t t; int a[N];
Заполняется массив a[N] значениями от 0 до 99
Выводится на экран длина массива N и найденные значения x, n
Выполняется бинарный поиск с помощью функции binsearch
Выполняется бинарный поиск с помощью функции binsearch2
Выполняется бинарный поиск с помощью функции binsearch3
Все функции имеют одинаковый прототип: int x, int a[], int n
В функции binsearch происходит бинарный поиск элемента x в массиве a с использованием переменных l, h, m
В функции binsearch2 происходит бинарный поиск элемента x в массиве a с использованием переменных l, h, m, и проверкой на равенство a[m] элементу x
В функции binsearch3 происходит бинарный поиск элемента x в массиве v с использованием переменных low, high, mid
Если элемент x найден, то возвращается его позиция, иначе возвращается -1
Если элемент x не найден ни в одной из функций, то выводится на экран сообщение об ошибке