c++ - 二进制搜索插入字符字符串。错误在哪里？

Question

我有字符串数组。我必须通过二进制搜索算法在字符串数组中找到一个字符字符串。如果存在这个字符串，则函数必须返回位置并返回真，否则该函数必须返回在数组中插入字符串的位置和假。我在某个地方有错误，但我不知道在哪里（（

例子：

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;
}

Answer 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;
}

Answer 2

我想也许应该是：

if ( for_compare > 0 )
{
    end = middle - 1;
} 
else if ( for_compare < 0 )
{
    start = middle + 1;
}