Двоичный поиск не возвращает правильное значение

Question

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

template<class T> 
int binary_search(T search_value, T search_array[]) { 

    int mid; /* The middle element of the remaining array to be searched. */ 
    int min = 0; /* The first index of the array. */ 
    /* This forumla gives us the size of the array. */ 
    int max = sizeof(search_array)/sizeof(search_array[0]); 

    /* Continue searching until min >= max. */ 
    while (min < max) { 
     /* Compute the value of mid using a formula that won't produce a number 
     * larger than the maximum allowed value of an integer. */ 
     mid = (max-min)/2 + min; 

     /* Depending the whether search_value is larger or smaller than the 
     * value of whatever is at search_array[mid], set one of mid and max 
     * equal to mid. */ 
     if (search_value > search_array[mid]) 
      min = mid + 1; 
     else if (search_value < search_array[mid]) 
      max = mid + 1; 
     else { 
      return mid; 
     } 
    } 

    return -1; 
} 

Учитывая массив {0, 1, 3, 5, 7, 9} и поиска 3, функция должна возвращать 2, индекс 3 в массиве. Моя функция возвращает -1, что означает, что 3 не найден в массиве. Где проблема?

Answer 1

int max = sizeof(search_array)/sizeof(search_array[0]); 

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

Передайте размер вашего массива в качестве параметра вашей функции, это самый простой подход.

Answer 2

Там ошибка в вашей реализации:

else if (search_value < search_array[mid]) 
    max = mid + 1; 

должно быть:

max = mid - 1; 

Answer 3

Эта линия является, по крайней мере одна проблема:

int max = sizeof(search_array)/sizeof(search_array[0]); 

Массивы не передаются через , поэтому ваше заявление:

int binary_search(T search_value, T search_array[]) 

... так же, как:

int binary_search(T search_value, T *search_array) 

И таким образом max является размер указателя, деленному на размер элемента, так что в лучшем случае это может быть до 6, но большинство вероятно, является 0 или 1.

Я думаю, что в C++ вы можете передать массив по ссылке и узнать размер, используя форму заявления, как это:

template <size_t array_length> 
void foo (const char (&data) [array_length]) 
{ 
    // ... 
} 

Answer 4

Эта линия не делает то, что вы думаете, что лань s:

int max = sizeof(search_array)/sizeof(search_array[0]); 

Поскольку массивы автоматически распадаться на указатели при передаче в функцию это будет эффективно равно это:

int max = sizeof(void*)/sizeof(search_array[0]); 

Который не то, что вы хотели. Либо используйте std::vector, где хранится размер для вас или ручной аргумент size_t array_length.

Answer 5

int max = sizeof(search_array)/sizeof(search_array[0]); 

search_array - указатель не массив.

Параметр массива типа T в прототипе функции автоматически настраивается на указатель на T.

Answer 6

Эта линия в отношении:

int max = sizeof(search_array)/sizeof(search_array[0]); 

sizeof(search_array) будет размер указателя, 4 или 8 байт в зависимости от платформы.Как правило, я стараюсь избегать использования sizeof для переменных. Он лучше всего используется для типов. Например, в вашем случае sizeof(T).

Answer 7

Ваша максимальная должна быть один меньше, так как индекс начинается с 0.