在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二進制搜索

回答

相關問題