C++二進制搜索算法不起作用

所以我有一個名爲bList的ints矢量，它已經有了信息。我在運行二進制搜索之前對它進行了排序。C++二進制搜索算法不起作用

//I have already inserted random ints into the vector 


//Sort it 
bubbleSort(); 
//Empty Line for formatting 
cout << "\n"; 
//Print out sorted array. 
print(); 

cout << "It will now search for a value using binary search\n"; 

int val = binSearch(54354); 
cout<<val;

我的氣泡排序算法確實有效。

我讓它返回一個int，它是搜索值在列表中的位置。

//Its one argument is the value you are searching for. 
int binSearch(int isbn) { 
    int lower = 0; 
    int upper = 19;//Vector size is 20. 
    int middle = (lower + upper)/2; 

    while (lower < upper) { 
     middle = (lower + upper)/2; 
     int midVal = bList[middle]; 

     if (midVal == isbn) { 
      return middle; 
      break; 
     } else if (isbn > midVal) { 
      lower = midVal + 1; 
     } else if (isbn < midVal) { 
      upper - midVal - 1; 
     } 
    } 

}

但由於某種原因，當我運行它時，它只是繼續運行，並沒有返回任何東西。

來源

2013-10-03 Zeratas

我建議你通過代碼，行步一行一行，一個調試器。 –

請注意，'return'後面的'break'語句不是必需的。 –

如果您正在查找的值不在數組中，您將在不返回任何內容的情況下到達函數的結尾。你至少應該返回一些形式爲'value_not_found'的結尾。 – SirGuy

這裏的錯誤是：

// ... 
} else if (isbn > midVal) { 
    lower = midVal + 1; 
} else if (isbn < midVal) { 
    upper - midVal - 1; 
}

你可能想

lower = middle + 1;

和

upper = middle - 1;

代替。您還需要在找不到所需號碼時顯式返回某些內容。

來源

2013-10-03 15:06:40 timrau

Ahhhhhhh，愚蠢的錯誤，明白了，謝謝。我正在比較價值而不是位置。 – Zeratas

如果他正在搜索的值終止於其中一個末端（「下」或「上」），則他的搜索將無法找到結果（即使它位於向量中）。他的狀況是那裏的問題。 –

你仍然有輕微的邏輯問題與您while條件：

int binary_search(int i, const std::vector<int>& vec) // you really should pass in the vector, if not convert it to use iterators 
{ 
    int result = -1; // default return value if not found 
    int lower = 0; 
    int upper = vec.size() - 1; 

    while (lower <= upper) // this will let the search run when lower == upper (meaning the result is one of the ends) 
    { 
     int middle = (lower + upper)/2; 
     int val = vec[middle]; 

     if (val == i) 
     { 
      result = middle; 
      break; 
     } 
     else if (i > val) 
     { 
      lower = middle + 1; // you were setting it to the value instead of the index 
     } 
     else if (i < val) 
     { 
      upper = middle - 1; // same here 
     } 
    } 

    return result; // moved your return down here to always return something (avoids a compiler error) 
}

或者，你可以切換它使用迭代器來代替：

template<class RandomIterator> 
RandomIterator binary_search(int i, RandomIterator start, RandomIterator end) 
{ 
    RandomIterator result = end; 

    while (start <= end) // this will let the search run when start == end (meaning the result is one of the ends) 
    { 
     RandomIterator middle = start + ((end - start)/2); 

     if (*middle == i) 
     { 
      result = middle; 
      break; 
     } 
     else if (i > *middle) 
     { 
      start = middle + 1; 
     } 
     else if (i < *middle) 
     { 
      end = middle - 1; 
     } 
    } 

    return result; 
}

來源

2013-10-03 15:42:32

C++二進制搜索算法不起作用

回答

相關問題