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

我有一串字符串。我必须用二进制搜索算法在字符串数组中找到一个char字符串。如果有这一个字符串，则函数必须返回位置并返回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; 
}

来源

2013-04-09 user1779502

我觉得'char * arr_strings []'应该是'char arr_strings []'开始的，但这取决于您如何调用Binary_search。 – 2013-04-09 01:12:43

问题是什么？ – Arun 2013-04-09 01:13:37

@stardust_不，不应该。 – 2013-04-09 01:15:39

的问题是，您的插入位置不对

你应该这样做如下：

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

来源

2013-04-09 01:16:26 taocp

不错，但我很害怕这个算法会慢慢。我认为最后必须是两个IF或其他位置 – user1779502 2013-04-09 01:20:35

@ user1779502我刚刚更新了该帖子，现在它应该按照您的预期工作。我只用3个字符串进行测试，它工作正常（确定更改结束为2） – taocp 2013-04-09 01:31:23

感谢您的工作，但我仍然在使用此代码排序时出现了一些错误。也许错误是在别的地方。我必须使用这个函数来插入字符串。如果在数组中没有字符串，那么函数必须返回false，并且使用位置插入Im，否则函数返回true，并返回参考位置在数组fot下一个工作 – user1779502 2013-04-09 01:43:36

我想，也许应该是：

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

来源

2013-04-09 01:20:00 TerryZJ

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

回答

相关问题