Можно ли проводить только одно сравнение на итерацию алгоритма двоичного поиска?

Да. Только не удаляйте mid из рекурсивного вызова.

if ( left == right ) return NULL;
if ( left + 1 == right ) return key == a[left]? &a[left] : NULL;

mid = left + ( right - left / 2 );

if (key < a[mid]) return binary_search(a[],left,mid-1);
else return binary_search(a[],mid,right); // include `mid` in next round

Чтобы добиться производительности O (logN), вам нужно исключать только половину набора при каждой рекурсии. Вы делаете все возможное, удаляя половину + 1.

Если вы используете только < во время рекурсии, алгоритм найдет наименьший элемент, который не меньше, чем ключ (но может быть больше, чем ключ ). . Закончите, выполнив единственный тест на равенство.

На ассемблере вы можете:

cmp key,a[mid]
beq found
bge else

Так что, если ваш компилятор действительно хорош в оптимизации с помощью глазок, он, возможно, уже сделает это за вас.

Это рекурсивный алгоритм. Первое сравнение - это критерии остановки, а второе - фактический поиск, поэтому вы не можете их удалить.

Во-первых, вы спрашиваете, когда вы уже нашли элемент, а во-вторых, в какой части массива искать элемент. Таким образом, вы не можете принимать эти решения, основываясь только на одном сравнении.

Перво-наперво: нужно ли вам оптимизировать программу? Вы измерили, чтобы знать, где это нужно делать? Это в этой функции?

Для примитивных типов второе сравнение является максимально быстрой операцией. Более высокая стоимость сравнения - загрузка элемента в соответствующий регистр, и это необходимо для первого сравнения. Как только это сравнение выполнено, значение уже находится в регистре, и вторая операция требует одной инструкции процессора плюс возможные затраты на неверное предсказание перехода.

Предполагая целочисленные типы, в стоимости процессорного времени алгоритма, скорее всего, преобладает стоимость рекурсивных вызовов, если компилятор не может выполнить оптимизацию хвостовой рекурсии. Если вам действительно нужно оптимизировать это, попробуйте скомпилировать со всеми включенными флагами оптимизации и проанализируйте ассемблер, чтобы определить, применяется ли оптимизация хвостовой рекурсии. Если нет, вручную преобразуйте алгоритм из рекурсивного в итеративный.

Это будет иметь два эффекта: скрыть код (избегать изменения чистого решения, если в этом нет необходимости) и избежать вызовов функций.

Если вы говорите о C ++, а тип сложен, а перегруженные операторы сравнения дороги, самым быстрым приростом производительности является реализация метода compare , который вернет отрицательное число за меньше -тем , 0 для равного и положительное число, если больше, -чем . Затем предварительно вычислите результат перед сравнениями, а затем выполните только целочисленные проверки.Это снизит общую стоимость алгоритма до единственной обработки реальных объектов с дорогостоящим сравнением и вернет вас к исходному предположению.

for (step = 0; step < n; step <<= 1);

for (i = 0; step; step >>= 1)
    if (i + step < n && v[i + step] <= x)
        i += step;

Хорошо, это был вопрос интервью в Adobe, и я просто пытался понять, как это сделать.

Теперь у меня есть решение, поэтому я публикую

void binary_search (int a[] , int low ,  int high , int key )
{
    int mid = (low+high)/2;

    if (key == a[mid]) {
        printf ("Number Found\n");
        return;
    }

    else {
        int sign = Calc_sign (key-a[mid]);
        low = low*sign + (1-sign)*mid;
        high = mid*sign + (1-sign)*right;
        binary_search (a,low,high,key);
    }
}

int Calc_sign(int a) 
{
     return ( (a & 80000000) >> 31);
}

Итак, в коде будет только одно сравнение для проверки того, соответствует ли ключевое значение среднему элементу.

-

Спасибо

Алок Кр.