Как оптимизировать бинарный поиск?

Question

Я думал о том, как мой бинарный поиск можно оптимизировать. Код следует. Что я до сих пор делал:

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

Оптимизированный наихудший случай (один из наихудших случаев), когда элемент, находящийся в поиске, выходит за пределы, то есть ищет число, меньшее, чем самое низкое или выше самого высокого. Это сохраняет сравнение O (logn), когда оно является гарантией, что оно не будет найдено на входе.

int input[15] = {1,2,2,3,4,5,5,5,5,6,7,8,8,9,10}; 
/* 
* Returns index p if a[p] = value else -ve int. 
* value is value being searched in input. 
*/ 
int 
binary_search (int * input, int low, int high, int value) 
{ 
    int mid = 0; 
    if (!input) return -1; 
    if (low > high) return -1; 

    /* optimize worst case: value not in input */ 
    if ((value < input[low]) || (value > input[high])) 
    { return -2; } 

    mid = (low + high)/2; 

    if (input[mid] == value) { 
     return mid; 
    } 
    if (input[mid] > value) { 
     return binary_search(input, low, mid -1, value); 
    } else { 
     return binary_search(input, mid+1, high, value); 
    } 
} 

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

Любые другие предложения о том, в каких других областях я могу сосредоточиться на улучшении. Мне не нужен код, но направление было бы полезно. Благодарю.

Answer 1

Jon Bentley's Программирование Pearls имеет прекрасную главу об оптимизации бинарного поиска. Смотрите главу 4 в http://www.it.iitb.ac.in/~deepak/deepak/placement/Programming_pearls.pdf

Одним из вариантов является удивительно эффективным (см 87 в главе «Код Tuning»):

# Search a 1000-element array 
l = 0 
if x[512] < t: l = 1000 + 1 - 512 
if x[l+256] < t: l += 256 
if x[l+128] < t: l += 128 
if x[l+64] < t: l += 64 
if x[l+32] < t: l += 32 
if x[l+16] < t: l += 16 
if x[l+8] < t: l += 8 
if x[l+4] < t: l += 4 
if x[l+2] < t: l += 2 
if x[l+1] < t: l += 1 
p = l + 1 
if p > 1000 or x[p] != t: 
    p = 0     # Not Found 

Answer 2

Оптимизация сортировки, которую вы рассматриваете - обработка специального случая - неизбежно заставит вас тратить больше времени на ДРУГИЕ случаи. Оптимизация «худшего случая» сделала их лучшими, но ценой создания других худших случаев. И в этом случае вы делали два случая в «лучшие случаи» и n/2 дел в «худшие случаи», которых раньше не было. Вы все замедлили.

(особенно в данном случае, потому что вы проверяете слишком низкое/слишком высоко на каждый рекурсии.)

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