Оптимизация алгоритма двоичного поиска

Question

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

bool binSearch(int array[], int key, int left, int right) 
{ 

    mid = left + (right-left)/2; 
    if (key < array[mid]) 
     return binSearch(array, key, left, mid-1); 
    else if (key > array[mid]) 
     return binSearch(array, key, mid+1, right); 
    else if (key == array[mid]) 
     return TRUE; // Found 

    return FALSE; // Not Found 
} 

Answer 1

Я бы попробовал bsearch() стандартная функция сначала. Скорее всего, он работает лучше, чем ваш подход.

Answer 2

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

Дайте мне знать, если вам нужно больше деталей.

Answer 3

Для целых чисел это не имеет значения, не делайте этого.

Для более дорогих сравнений используйте -1, 0, 1 для <, =,> как в функции библиотеки C strcmp или в сравнении с Java.

Answer 4

Не рекомендуется пытаться оптимизировать то, как вы описываете. Из Binary Search Algorithm article on Wikipedia:

Около половины времени, первое испытание будет правдой, так что будет только одно сравнение а и Ь, а другая половина времени будет ложным, и второе сравнение вынуждены. Это настолько печально, что некоторые версии переработаны, чтобы не проводить второе испытание вообще, не определяя равенства до тех пор, пока диапазон не будет уменьшен до нуля и, следовательно, не будет иметь возможность досрочного расторжения - помните, что примерно в половине случаев, когда поиск будет происходят по совпадающему значению с одной итерацией до предела.

Это довольно легко сделать эту проблему еще хуже (например, как в 3) с использованием порядка, таких как

if a = b then action3 
else if a > b then action2 
    else action1; 

Вместо определения равенства рано (как это может показаться), это приведет к двум сравнениям для всех, кроме последней итерации поиска.

Некоторые языки, как Фортран, есть сравнение трехпозиционный, что позволяет этот шаг нужно сделать с одним сравнения, что ветви на трех различных секций (см десятую строчку Three-way comparison example). Если ваш язык не поддерживает трехсторонний тест (в большинстве языков нет), то два сравнения - это лучшее, что вы можете сделать.

I будет советую вам проверить iterative implementation из той же статьи.

Answer 5

В коде, который вы опубликовали, вы можете удалить последнее сравнение. То есть, если key составляет не менее array[mid] или больше array[mid], то по определению оно равно. Таким образом, ваш код будет:

mid = left + (right-left)/2; 
if (key < array[mid]) 
    return binSearch(array, key, left, mid-1); 
else if (key > array[mid]) 
    return binSearch(array, key, mid+1, right); 
else 
    return TRUE; // Found 

Также обратите внимание, что я удалил последнюю строку. В исходном коде невозможно выполнить return FALSE;. Я бы предположил, что у вас есть чек в начале вашего binSearch, который проверяет, есть ли left < = right.

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

Answer 6

Ganesh M - Если ключ не существует в массиве, тогда ваша функция будет застревать внутри бесконечного цикла. Он никогда не сможет вернуть FALSE.

Каков оптимальный способ найти точку вставки, если ключ не существует?

Условный «если каскад», учитывающий <, ==, и>, вернет TRUE или продолжит вычислять навсегда.

Мне нужно оптимальное условие, чтобы определить, когда ключ изолирован как не существующий.

Я знаю, что это замедлит поиск, но я хочу замедлить его на наименьшую сумму.

играет с журналом (N)/log (2), кажется хорошей идеей, но когда N не является силой 2, все может пойти поскорей.

Возможно, я должен выбрать массив с мощностью 2 и использовать простой цикл while?

проверяет, слишком ли значительна ли промежуточная точка == для того, чтобы увеличить количество сравнений?

Answer 7

Я попытался восстановить шаги оптимизации алгоритма бинарного поиска. Я начинаю с этого итеративного версии:

int binsearch_1(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    int found=0; 
    while(size > 0){ 
    size_t w=size/2; 
     if(p[w] < key ){ p+=w+1; size-=w+1; } 
    else if(p[w] > key ){   size =w; } 
    else /* p[w] == key */{ p+=w; found=1; break; } 
    } 
    *index=p-array; return found; 
} 

Устранение сравнений из цикла:

int binsearch_2(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 0){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    *index=p-array; return p[0]==key; 
} 

разворачивая небольшие размеры из цикла:

int binsearch_3(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 8){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    if(size==8){ if(p[5] <= key){ p+=5; size=3; } else size=4; } 
    if(size==7){ if(p[4] <= key){ p+=4; size=3; } else size=3; } 
    if(size==6){ if(p[4] <= key){ p+=4; size=2; } else size=3; } 
    if(size==5){ if(p[3] <= key){ p+=3; size=2; } else size=2; } 
    if(size==4){ if(p[3] <= key){ p+=3; size=1; } else size=2; } 
    if(size==3){ if(p[2] <= key){ p+=2; size=1; } else size=1; } 
    if(size==2){ if(p[2] <= key){ p+=2; size=0; } else size=1; } 
    if(size==1){ if(p[1] <= key){ p+=1;   }    } 
    *index=p-array; return p[0]==key; 
} 

переупорядочивания, если заявления, двигая специальные случаи [размер == pow (2, N) -1] до конца:

int binsearch_4(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 8){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    if(size==8){ if(p[5] <= key){ p+=5; size=3; } else size=4; } 
    if(size==6){ if(p[4] <= key){ p+=4; size=2; } else size=3; } 
    if(size==5){ if(p[3] <= key){ p+=3; size=2; } else size=2; } 
    if(size==4){ if(p[3] <= key){ p+=3; size=1; } else size=2; } 
    if(size==2){ if(p[2] <= key){ p+=2; size=0; } else size=1; } 

    if(size==7){ if(p[4] <= key){ p+=4; size=3; } else size=3; } 
    if(size==3){ if(p[2] <= key){ p+=2; size=1; } else size=1; } 
    if(size==1){ if(p[1] <= key){ p+=1;   }    } 
    *index=p-array; return p[0]==key; 
} 

Изменение, если заявления на распределительном заявление:

int binsearch_5(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 8){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    if(size==8){ if(p[5] <= key){ p+=5; size=3; } else size=4; } 
    if(size==6){ if(p[4] <= key){ p+=4; size=2; } else size=3; } 
    if(size==5){ if(p[3] <= key){ p+=3; size=2; } else size=2; } 
    if(size==4){ if(p[3] <= key){ p+=3; size=1; } else size=2; } 
    if(size==2){ if(p[2] <= key){ p+=2; size=0; } else size=1; } 

    switch(size){ 
    case 7: if(p[4] <= key) p+=4; 
    case 3: if(p[2] <= key) p+=2; 
    case 1: if(p[1] <= key) p+=1; 
    } 
    *index=p-array; return p[0]==key; 
} 

Расширение переключателя заявление для обработки всех специальных случаев:

int binsearch_6(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    switch(size){ 
#define C(n) case ((size_t)1<<n)-1: if(p[1<<(n-1)]<=key) p+=1<<(n-1); 
#if SIZE_MAX == UINT64_MAX 
               C(63) C(62) C(61) 
    C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51) 
    C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41) 
    C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32) 
#endif 
                  C(31) 
    C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21) 
    C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11) 
    C(10) C(9) C(8) C(7) C(6) C(5) C(4) C(3) C(2) C(1) 
#undef C 
     break; 
    default: 
     while(size > 0){ 
     size_t w=size/2; 
     if(p[w] < key){ p+=w+1; size-=w+1; } else size=w; 
     } 
    } 
    *index=p-array; return p[0]==key; 
} 

Исключая общую обработку из кода случай: [ш наименьшее число : w = pow (2, N) -1; Размер < = 2 * (W + 1)]

int binsearch_7(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    size_t w=(size-1)>>1; w|=w>>1; w|=w>>2; w|=w>>4; w|=w>>8; w|=w>>16; 
#if SIZE_MAX == UINT64_MAX 
    w|=w>>32; 
#endif 
    if(p[w]<key) p+=size-w-1; 
    switch(w){ 
#define C(n) case ((size_t)1<<n)-1: if(p[1<<(n-1)]<=key) p+=1<<(n-1); 
#if SIZE_MAX == UINT64_MAX 
               C(63) C(62) C(61) 
    C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51) 
    C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41) 
    C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32) 
#endif 
                  C(31) 
    C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21) 
    C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11) 
    C(10) C(9) C(8) C(7) C(6) C(5) C(4) C(3) C(2) C(1) 
#undef C 
    } 
    *index=p-array; return p[0]==key; 
} 

Последний шаг, что я сделал был упрощающим из этикетками [из: '((size_t) 1 < < п) -1', чтобы: ' n '], но я обнаружил, что модифицированный код был медленнее на моем старом компьютере, чем предыдущая версия.

Answer 8

// Optimized Binary Search Implementation 
int binsearch(int* data, int size, int val) 
{ 
    int result = -1; 
    int start, mid, end; 
    start = 0; 
    end = size - 1; 
    mid = (start + end) >> 1; 
    while (start <= end && data[mid] != val) 
    { 
     if (data[mid] > val) 
      end = mid - 1; 
     else 
      start = mid + 1; 
     mid = (start + end) >> 1; 
    } 
    if (val == data[mid]) 
     result = mid; 
    return result; 
} 

Answer 9

Его вопрос об осуществлении в K & R второе издание.

While(low <= high && arr[mid]!=num) 
{ 
    if(arr[mid] > num) 
    { 
     low = mid+1; 
    } 
    else 
    { 
     high = mid-1; 
    } 
    mid = (low+high)/2; 
} 

if(arr[mid] == num) 
{ 
    printf("found the ugly number"); 
    return mid; 
} 

Answer 10

BinarySearch = function (array, value) 
{ 
    var l = 0; 
    var r = array.length; 
    var mid; 
    while (l!=r) 
    { 
     mid = Math.round((r+l)/2)-1; 
     if(value > array[mid]) 
      l=mid+1; 
     else 
      r=mid; 
    } 
    if(array[mid]==value) 
     return mid; 
    else 
    { 
     if((mid < (array.length-1)) && (array[mid+1]==value)) 
      return mid+1; 
     else 
      return -1; // Not found 
    } 
} 

Источник: http://calcs.appspot.com/docview?id=agVjYWxjc3IPCxIIRG9jdW1lbnQY0w8M

Answer 11

bool binSearch(int array[], int key, int len) 
{ 
    int mid, low, high; 

    low = 0; 
    right = len - 1; 
    mid = low + (high-low)/2; 

    while ((low <= high) && (array[mid] != key)) { 
     if (key < array[mid]) { 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     } 
     mid = low + (high-low)/2; 
    } 

    if (array[mid] == key) { 
     return TRUE; 
    } 
    return FALSE; 
}