Рекурсивный двоичный поиск на С++
169
25 апреля 2017, 08:38
День добрый. Реализовал рекурсивный двоичный поиск, но время от времени переполняется стек. В чем проблема?
int bin_search(vector<int> & arr, int left, int right, int number) {
int mid = left / 2 + right / 2;
if (left > right) {
return -1;
}
if (left <= right) {
if (number == arr[mid]) {
return mid;
}
else if (number > arr[mid]) {
bin_search(arr, mid + 1, right, number);
}
else {
bin_search(arr, left, mid - 1, number);
}
}
}
Answer 1
Первое, то нашел - это следующая строка
int mid = left / 2 + right / 2;
она не всегда ищет "середину". допустим, что left и right равны 1, тогда mid будет равно 0. А это не совсем то, что ожидается. Если взять два других нечетных числа, то будет такая же ситуация или около того. Например, при 3 и 5, середина у Вас получается 3 (1 + 2)
при двух 1 эта строка скорее всего и приводит к зацикливанию.
Как избежать подобных ошибок? добавьте в список #include <cassert>, а в коде после данного вычисления добавьте такое
assert(mid >= left);
assert(right>=mid);
и ошибка сама всплывет.
-
21:33
Виртуальный выделенный сервер (VDS) становится отличным выбором
-
22:26
-
22:40
-
08:34
-
15:01
-
17:01
-
11:24
-
10:16
-
17:54
ТОП-10
- Почему SERVER_ADDR имеет не тот IP 47692 visits
- Как заменить $_SERVER[REMOTE_ADDR] на IP клиента в PHP за двумя Nginx? 30541 visits
- Хочу вывести несколько строк из массива в один div, выводит только много undefined; подскажите, что делать? 23719 visits
- Как через css изменить цвет png изображения? 10371 visits
- Blob video url download 9979 visits
- Php curl запрос через прокси с авторизацией 9238 visits
- Работа с captcha vk api 8114 visits
© "hostciti.net" 21.1.2025 | 11:52