在cs50中陷入while循环pset3二进制搜索

-1

我试图使用while循环实现二分搜索。它似乎工作时，我正在寻找int是在阵列中;但是，当我搜索的int不存在时，该程序似乎卡在循环中，没有返回false。我一直在使用gdb，但我仍然无法弄清楚这个bug。正如你所看到的，我可能会添加一些额外的if语句等，试图弄清楚这一点。在cs50中陷入while循环pset3二进制搜索

bool search(int value, int values[], int n) { 
    sort(values, n); 

    int begin = 0; 
    int end = (n - 1); 

    if (n < 1) { 
     return false; 
    } 
    while (end > begin + 1) { 
     int center = ((begin + end)/2); 
     if (values[0] == value) { 
      return true; 
     } 
     if (begin == value) { 
      return true; 
     } 
     if (end == value) { 
      return true; 
     } 
     if (end == (begin + 1) || end == begin) { 
      if (end == value || begin == value) { 
       return true; 
      } else { 
       return false; 
      } 
     } 
     if ((values[center]) == value) { 
      return true; 
     } else 
     if ((values[center]) > value) { 
      end = center; 
     } else 
     if ((values[center]) < value) { 
      begin = center; 
     } else { 
      return false; 
     } 
    } 
    // TODO: implement a searching algorithm 
    return false; 
}

来源

2016-11-23 aknys

'begin'和'end'被索引，你为什么与'value'比较它们？ – Barmar

在SO上有很多可用的二进制搜索算法（这里肯定会有，并且它们中的相当一部分也会与CS50相关）。你应该看看其中的一些，看看你的代码是非常复杂和不正确的。例如，[C中的二进制搜索的首次和最后一次出现]中有有用的代码（http://stackoverflow.com/questions/35147784/），它处理比您需要的一些更复杂的情况，但也包含代码你需要。你可以看看[如果语句不能识别真实条件]（http://stackoverflow.com/questions/38468878/）。 –

@aknys：您可以通过点击其分数下方的灰色复选标记来接受其中一个答案。 – chqrlie

为什么你这样做？

if (values[0]==value) 
    { 
     return true; 
    } 
    if (begin == value) 
    { 
     return true; 
    } 
    if (end == value) 
    { 
     return true; 
    } 
    if (end == (begin+1) || end == begin) 
    { 
     if (end == value || begin == value) 
     { 
     return true; 
     } 
     else 
     { 
     return false; 
     } 
    }

他们没有必要。你可以这样做，就像下面

while(end>beg+1 && values[center]!=value) 
    { 
    if ((values[center])>value) 
     end = center-1; 
    else if (values[center]<value) 
     begin = center+1; 
    center=(end+begin)/2; 
    } 
    if(values[center]==value) 
      return true; 
    else return false; 
    }

而且我不明白为什么你用sort(values,n); 如果是C++代码，然后用它作为sort(values,values+n); ，如果它是一个C代码，然后使用任何数组排序算法根据您的阵列大小和时间。谢谢。

来源

2016-11-24 04:15:12

你不必要的过分复杂这个简单的事情。你可以仅仅删除所有多余的东西在你的代码，并使用这个

`if ((values[center])==value) 
    { 
     return true; 
    } 
    else if ((values[center])>value) 
    { 
     end = center-1; 
    } 
    else if ((values[center])<value) 
    { 
     begin = center+1; 
    }

来源

2016-11-27 23:51:05

您的代码过于复杂。下面是一些提示：

您应该使用范围与包括左手食指和排除正确的索引，这是在C语言习惯，并导致简单的算法。
如果start和end非常大，您应计算center = start + (end - start)/2;而不是center = (start + end)/2;以避免潜在的整数溢出。
数组大小应为size_t，可能大于int。
- 如果相等，价值被发现，返回true：
- 在范围的中间比较，该元素的值。
- 如果较小，则将范围缩小到左侧部分，中间排除。
- 否则将范围缩小到右侧部分，排除中心。
如果范围为空，则未找到该值，则返回false。

下面是一个简单的版本：

bool search(int value, int values[], size_t n) { 
    // Assuming values is sorted before calling this function 
    //sort(values, n); 

    size_t begin = 0; 
    size_t end = n; 

    while (begin < end) { 
     size_t center = begin + (end - begin)/2; 
     if (value == values[center]) { 
      return true; 
     } 
     if (value < values[center]) { 
      end = center; 
     } else { 
      begin = center + 1; 
     } 
    } 
    return false; 
}

来源

2016-11-28 00:01:52 chqrlie

在cs50中陷入while循环pset3二进制搜索

回答

相关问题