Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
#include <iostream>
#include <cstdlib>
using namespace std;
int bin_search(int *A, int key, int low, int high){
if (low > high){
return 0;
}
int mid = ( low + high ) / 2;
if (A[mid] == key)
return mid+1;
else if( A[mid] < key)
bin_search(A, key, mid + 1, high);
else if (A[mid] > key)
bin_search(A, key, low, mid - 1);
}
int main()
{
int n, k;
cin >> k >> n;
int A[n-1];
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
cout << bin_search(A, k, 0, n);
}
Нужно реализовать бинпоиск рекурсией, на вход значение искомого элемента,
число элементов и сам массив,
вывести номер минимального элемента равного искомому.
У меня откровенно говоря баг, не могу его откопать, помогите!!!
Оно, конечно, иногда дает копеечку перфоманса, если на n наложены ограничения, и оно невелико, да и покороче, чем вызов alloca... Но толпы обезьян, которые побегут это юзать (т.к. короче чем std::vector), а потом начнут вопить что у них порвало стек, нивелируют все преимущества 😉
Требуется найти число K в упорядоченном массиве из N элементов и
определить чему равен номер соответствующего элемента массива.
Если элемент не найден, то вывести 0.
Входные данные
В первой строке расположено искомое число К.
Во второй - количество элементов в массиве N <= 10000.
Далее расположены N целых чисел, упорядоченных по возрастанию.
Выходные данные
Выведите наименьший номер найденного значения, или 0, если элемент не найден.
Что-то сомнительно, что он выйдет (если учитывать, что в строке 27 баг уже пофиксили, и там n-1, а не n)...
Переполнение и залет в минус будет только на 16-битном компилере при n в районе 32к, или на 32-битном при n в районе двух лярдов. Оба случая маловероятны.
А ну да. На выхлопе нет перевода строки. std::endl добавляй, должно пролететь 🙂
P.S. Что-то косяки настолько простые, что я уже давным-давно не видел их в коде, с которым работаю, и из-за этого потерял на них нюх, и тупо в упор не вижу... Что этот endl, что return, что A[n-1]... А может просто пора спать...
По идее трабла в том, что ты в строке 27 передал n, вместо n-1. А весь остальной код в bin_search рассчитан на закрытые интервалы [low; high], а не на полуоткрытые [low; high), которые получаются из-за этого бага.
Затем, что это не perl и не ruby какое-нибудь, где результат последнего стейтмента автоматом считается результатом функции 😉
Это хардкорные кресты, которые не прощают ошибок (и, компиляторы зачастую, не говорят о них).
Функция, которая должна была вернуть int, но завершилась, не сделав этого, имеет полное право вернуть мусор... Или вернуть правильный ответ... Никто не знает что именно произойдет. Это UB.
Алексей, задания в СУНЦ задаются для того, чтобы их делать самостоятельно. В крайнем случае можно было спросить одноклассников.
На лекциях вам рассказывалось, какой в правом и левом бинпоиске должен быть инвариант, и что строки "if (A[mid] == key) return mid+1;" быть не должно, если нужен не произвольный элемент, равный заданному, а самый правый или самый левый.
питух - злая анскильная ничтожная сторона Царя
питух и Царь - неделимы, как инь и янь, как ленин и партия, как левое яйцо и правое яйцо
питушино-царский когнитивный дуализм
А в чём баг заключается?
Выдаёт не минимальный номер если есть несколько совпадающих значений?
Так у тебя нет проверки на то, что номер найденного элемента — минимальный.
Не работает на не отсортированных массивах?
Так и не должен.
Ну и еботня с индексами и указателем на оригинальный массив вместо двух указателей — тоже говно.
Оно, конечно, иногда дает копеечку перфоманса, если на n наложены ограничения, и оно невелико, да и покороче, чем вызов alloca... Но толпы обезьян, которые побегут это юзать (т.к. короче чем std::vector), а потом начнут вопить что у них порвало стек, нивелируют все преимущества 😉
определить чему равен номер соответствующего элемента массива.
Если элемент не найден, то вывести 0.
Входные данные
В первой строке расположено искомое число К.
Во второй - количество элементов в массиве N <= 10000.
Далее расположены N целых чисел, упорядоченных по возрастанию.
Выходные данные
Выведите наименьший номер найденного значения, или 0, если элемент не найден.
Почему бы не взять std::lower_bound из <algorithm>?
2. mid принимает питушарские значения.
Переполнение и залет в минус будет только на 16-битном компилере при n в районе 32к, или на 32-битном при n в районе двух лярдов. Оба случая маловероятны.
Или я совсем туплю?
Значит, скорее всего, или ввод или вывод багует. На контрольном примере, который в задании, все работает?
P.S. Что-то косяки настолько простые, что я уже давным-давно не видел их в коде, с которым работаю, и из-за этого потерял на них нюх, и тупо в упор не вижу... Что этот endl, что return, что A[n-1]... А может просто пора спать...
n-1 же... обсуждалось же ниже.
Прошел?
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
cout << bin_search(A, k, 0, n-1) << endl;
}
if (low > high){
return 0;
}
int mid = ( low + high ) / 2;
if (A[mid] == key)
return mid+1;
else if( A[mid] < key)
return bin_search(A, key, mid + 1, high);
else if (A[mid] > key)
return bin_search(A, key, low, mid - 1);
}
int main()
{
int n, k;
cin >> k >> n;
int A[n-1];
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
cout << bin_search(A, k, 0, n-1) << endl;
}
Проверь на данных:
4
8
1 4 4 4 4 4 4 9
и ты обнаружишь, что твоя программа не выдаёт 2, как должна.
Это цена велосипедостроительства.
Если там есть такой тест - то условие, имхо, неполное. Тут же не сказано upper bound искать, lower bound, или же вообще любое подходящее:
найти число K в упорядоченном массиве из N элементов и
определить чему равен номер соответствующего элемента массива
> Выведите наименьший номер найденного значения, или 0, если элемент не найден.
Разберись с принципом работы алгоритма, переделай итерацию в рекурсию и всё заработает.
Тьфу ёпт. Точно. Всё, я пошел спать, невнимательность прёт изо всех щелей 😉
В крестах это гццизм: http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Variable-Length.html. Если хочется портабельности - лучше не юзать VLA за пределами чистой сишки 😉
Если int A[n-1] будет иметь n элементов, то этот гццизм - питушня. Если int A[n-1] не будет иметь n элементов, то код - питушня.
Это заодно ответ на вопрос о n>100000 и даже о n>100000000.
P.S. ГК это не место для исправления лаб.
Ибо сишка, а не пасцаль. Ты только что словил buffer overflow, запилив массив на один элемент меньше, чем положено 🙂
Спасибо в карман не положишь 😉
Тест то прошел, или дальше мучаем?
P.S. Все, мне пора спать, таких очевидных косяков не вижу. С тебя пиво 😉
Это хардкорные кресты, которые не прощают ошибок (и, компиляторы зачастую, не говорят о них).
Функция, которая должна была вернуть int, но завершилась, не сделав этого, имеет полное право вернуть мусор... Или вернуть правильный ответ... Никто не знает что именно произойдет. Это UB.
В жопу.
return bin_search(A, key, mid + 1, high);
Прошел тест?
На лекциях вам рассказывалось, какой в правом и левом бинпоиске должен быть инвариант, и что строки "if (A[mid] == key) return mid+1;" быть не должно, если нужен не произвольный элемент, равный заданному, а самый правый или самый левый.
питух и Царь - неделимы, как инь и янь, как ленин и партия, как левое яйцо и правое яйцо
питушино-царский когнитивный дуализм
на питоне он уничтожается легко [python] del Царь [/python]
в них вся мудрость поколений и советы лучших птицеводов
> Царь - злая анскильная сторона питуха
Мощно!