поиск элемента в массив Опции

[compiler]

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

/* 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;
}

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

[volvo]

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

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

Спойлер (Показать/Скрыть)

Решение на основе инварианта. Будем считать, что v[low] < X <= v[high], при этом low < high... Также допустим, что v[-1] заведомо меньше X и v[n] больше или равно X (хотя элементов с индексами -1 и n нет, но предположение-то такое сделать можно?)... Теперь:

int binsearch2(int x, int v[], int n)
{
    int low, high, mid;
    low = -1; high = n; // инициализируем инвариант
    while(low + 1 != high) {
        mid = (low + high) / 2;
        
        if(v[mid] < x) low = mid;
        else high = mid;
      }

      // если X присутствует в массиве - его позиция возвращается в переменной high.
      // Но если high выходит за допустимые рамки (>= n) или элемент с индексом high
      // не является искомым - то вернуть -1 (элемент отсутствует)
      int result = high;
      if(result >= n || v[result] != x) result = -1;
      return result;
}

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

[compiler]

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

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

[compiler]

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

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 - 2.01.2008 23:10