Эффективный бинарный поиск - PullRequest
Новая
       8

Эффективный бинарный поиск

0 голосов
/ 26 мая 2019

Из двух разных реализаций бинарного поиска, какая из них более эффективна и почему?

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

int a[8] = {1, 3, 4, 5, 7, 8, 9, 11};

1. 

while ( size > 1)
{
    mid = low + (size/2);
    if (a[mid] > find)
    {
       size = mid - low;
    }
    else
    {
        size = size - (mid - low);
        low = mid;
    }
}

2. 

while (low <= size)
{
    mid = (low + size)/2;
    if (a[mid] < find)
    {
        low = mid + 1;
    }
    else if (a[mid] > find)
    {
        size = mid - 1;
    }
    else
    {
        break;
    } 
}

Покаища 6, первый итерирует как 

mid = 4 size = 4 low = 0
mid = 2 size = 2 low = 2
mid = 3 size = 1 low = 3
5

, а второй делает еще один итерацию и принимает следующую запись. 

mid = 4 size = 3 low = 0
mid = 1 size = 3 low = 2
mid = 2 size = 3 low = 3
mid = 3 size = 3 low = 4
7

Какой из них эффективен?

...