Двоичный поиск для вставки строки символов. Где ошибка?
У меня есть массив строк. Я должен найти одну строку символов в массиве строк с помощью алгоритма двоичного поиска. Если есть эта одна строка, то функция должна возвращать позицию и возвращать true, иначе эта функция должна возвращать позицию для вставки строки в массив и false.
У меня где-то ошибка, но я не знаю, где ((
Пример:
bool Binary_search ( char * arr_strings[], int & position, const char * search_string )
{
int start = 0 ;
int end = 10 - 1; // arr_strings [10]
int for_compare;
int middle;
while ( start <= end )
{
middle = ( start + end ) / 2;
for_compare = strcmp ( arr_strings[middle], search_string );
if ( for_compare > 0 )
{
start = middle + 1;
}
else if ( for_compare < 0 )
{
end = middle - 1;
}
else
{
// if search_string is found in array, then function return position in array of strings and return true
position = middle;
return true;
}
}
// if search_string is not found in array, then function must return position for insert string and return false
position = middle;
return false;
}
Решение
Я думаю, может быть, это должно быть:
if ( for_compare > 0 )
{
end = middle - 1;
}
else if ( for_compare < 0 )
{
start = middle + 1;
}
Другие решения
Проблема в том, что ваша позиция вставки неверна.
Вы должны сделать что-то вроде следующего:
bool Binary_search ( char * arr_strings[], const char * search_string )
{ //^^^you are not doing recursive, so you don't need position as parameter
int start = 0 ;
int end = 10 - 1; // arr_strings [10]
int for_compare;
int middle;
int position = -1;
while ( start <= end )
{
middle = ( start + end ) / 2;
for_compare = strcmp ( arr_strings[middle], search_string );
if ( for_compare > 0 )
{ //^^^here should switch the order
end = middle - 1;
}
else if ( for_compare < 0 )
{
start = middle + 1;
}
else
{
position = middle;
return true;
}
}
if (position == -1)
{
if(strcmp(arr_strings[middle],search_string) <0 )
{
position = middle + 1;
}else
{
position = middle;
}
}
return position;
}