Функция поиска только иногда работает

Question

Я пытаюсь сделать бинарную функцию поиска, и это мой текущий код:

bool _search(int value, int values[], int start, int end); 

/* 
* Main search function 
*/ 
bool search(int value, int values[], int n) { 
    if(value < 0) 
      return false; 
    sort(values, n); 
    return _search(value, values, 0, n); 
} 

bool _search(int value, int values[], int start, int end) { 
    if(start < end) { 
     // get the mean for comparing 
     int mean = (start + end)/2; 
     if(value == values[mean]) // middle 
      return true; 
     else if(value < values[mean]) // left half 
      return _search(value, values, start, mean - 1); 
     else // right half 
      return _search(value, values, mean + 1, end); 
    } else 
     return false; 
} 

Я передаю в случайных чисел в программе с постоянным семенем, и если количество чисел, которые я передаю, составляет 861 или ниже, оно работает правильно. Однако, если он получает 862 или более высокие номера, он не может найти значения. Weird. Поэтому я попытался пройти очень большое количество, скажем, 1862 года. Он нашел это! Хорошо ... как насчет 2000? Неа. 3000? Ага. 4000? Неа. 5000? Неа. 6000? Ага.

Что здесь происходит?

Редактировать: Кроме того, если массив имеет только 3 элемента, а искомый элемент - это первый элемент, он не будет найден. В алгоритме определенно что-то не так, я просто не могу погладить его.

Answer 1

Ваша функция search неправильная: start включен, но end не должен быть включен. Когда вы рекурсируете, вы не должны останавливаться на mean - 1, но в mean в противном случае вы пропустите некоторые записи, и поиск может завершиться неудачно, когда это не произойдет.

Вот исправленная версия:

bool _search(int value, int values[], int start, int end) { 
    if (start < end) { 
     // get the mean for comparing 
     int mean = (start + end)/2; 
     if (value == values[mean]) // middle 
      return true; 
     else 
     if (value < values[mean]) // left half 
      return _search(value, values, start, mean); 
     else // right half 
      return _search(value, values, mean + 1, end); 
    } else { 
     return false; 
    } 
}