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

Question

В алгоритме двоичного поиска у нас есть два сравнения:

if (key == a[mid]) then found;

else if (key < a[mid]) then binary_search(a[],left,mid-1);
      else binary_search(a[],mid+1,right);

Есть ли способ, которым я могу иметь только одно сравнение вместо двух вышеупомянутых.

-

Спасибо

Алок.Кр.

Answer 1

См:

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

Взято из вики:

   low = 0
   high = N
   while (low < high) {
       mid = low + ((high - low) / 2)
       if (A[mid] < value)
           low = mid + 1;
       else
            //can't be high = mid-1: here A[mid] >= value,
            //so high can't be < mid if A[mid] == value
            high = mid;
   }
   // high == low, using high or low depends on taste
   if ((low < N) && (A[low] == value))
       return low // found
   else
       return -1 // not found

Плюсы / минусы из вики: «Этот подход исключает возможность досрочного завершения при обнаружении совпадения, поэтому успешные поиски имеют итерации log2 (N) вместо ожидаемых итераций log2 (N) - 1. С другой стороны, эта реализация делает меньше сравнений: log2 (N ) меньше ожидаемого числа сравнений для реализаций с двумя тестами 1 · 5 (log2 (N) - 1), для N больше восьми. "

Answer 2

Да.Только не исключайте 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.

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

Answer 3

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

cmp key,a[mid]
beq found
bge else

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

Answer 4

Хорошо, это был вопрос интервью в 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);
}

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

-

Спасибо

Алок Кр.

Answer 5

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

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

Answer 6

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

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

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

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

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

Answer 7

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

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