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

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

ничего кроме

int binsearch2(int x, int v[], int n)
{
        int i;
        for(i=0; i<n; ++i) if (v[i]=x) return i;
        return -1;
}

в голову не идет...
а как правильно?
заранее благодарен.

K&R мучаешь? А есть ли смысл тогда просить подсказку?

Добавлено через 9 мин.
Если все-таки хочешь посмотреть на цикл с одним сравнением - то:



Сообщение отредактировано: volvo - 3.01.2008 5:41

думаешь не стоит... ладно, подумаю еще сам...

вот что я еще придумал...

int binsearch4(int x, int v[], int n){
        int low = 0;
        int high = n-1;
        int mid=((low + high) / 2);
        while ((x!=v[mid]) && (low!=high)){
                if (x < v[mid])
                        high = mid - 1;
                else
                        low = mid+1;
                mid = (low + high) / 2;
        }
        if (x==v[mid]) return mid; /*else*/
        return -1;
}

тут, правда, в условии цикла дабавленно условие... сейчас посмотрю твой код...

upd
volvo, не мог бы ты снабдить свой код комментариями(особенно часть после цикла), а зоодно оценить мой код...

Сообщение отредактировано: compiler - 3.01.2008 3:10