我正在嘗試執行二進制搜索以查找向量中特定元素的索引。我嘗試獲取第一個和最后一個元素并將它們傳遞給變數 high 和 low。我收到某種轉換錯誤。錯誤在 BinarySearchVector 函式內部。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int limit=10;
vector <int> elements;
void AddValueToVector(){
cout<<"Hello World:"<<endl;
for (int i = 0; i < limit; i )
{
int a;
cin>>a;
elements.push_back(a);
}
}
void printContents(){
cout<<"Vector elements:"<<endl;
for (int j = 0; j < limit; j )
{
cout<<elements[j]<<endl;
}
}
int binarySearchVector(vector<int>&elements,int searchval){
sort(elements.begin(),elements.end());
auto low= elements.begin();
auto high= elements.end();
while (low <= high) {
int mid = low (high - low) / 2;
if (elements[mid] == searchval)
return mid;
if (elements[mid] < searchval)
low = mid 1;
else
high = mid - 1;
}
return -1;
}
void search(){
int searchval;
cout<<"Enter value to search:"<<endl;
cin>>searchval;
int result= binarySearchVector(elements,searchval);
if (result==-1)
{
cout<<"Not Found"<<endl;
}else{
cout<<"Element is found at index"<<result<<endl;
}
}
int main()
{
AddValueToVector();
printContents();
search();
return 0;
}
任何建議將不勝感激。
uj5u.com熱心網友回復：
由于您的binarySearchVector函式應該回傳找到的元素的索引（不是迭代器），因此您可能不應該使用begin()and end()（回傳迭代器，而不是索引）。
例子：
int binarySearchVector(std::vector<int>& elements, int searchval) {
std::sort(elements.begin(), elements.end());
int low = 0; // index of first element
int high = elements.size() - 1; // index of last element
while (low <= high) {
int mid = low (high - low) / 2;
if (elements[mid] < searchval)
low = mid 1;
else if (elements[mid] > searchval)
high = mid - 1;
else
return mid;
}
return -1;
}
uj5u.com熱心網友回復：
你的意思是
int mid = *low (*high - *low) / 2;
迭代器實際上是指向元素的指標。如果你想要元素本身，你需要取消參考它
uj5u.com熱心網友回復：
要使用二進制搜索方法，您需要對向量進行排序。
變數low和high是迭代器
auto low= elements.begin();
auto high= elements.end();
沒有將迭代器隱式轉換為int您嘗試執行的型別的物件
while (low <= high) {
int mid = low (high - low) / 2;
//...
你至少需要寫
auto mid = low (high - low) / 2;
要么
auto mid = std::next( low, std::distance( low, high ) / 2 );
此外，回圈中的條件
while (low <= high) {
對于空子范圍是不正確的，因為在這種情況下，當low等于high回圈體時將獲得控制權，并且在回圈體內帶有迭代器的操作將呼叫未定義的行為。你需要寫
while (low < high) {
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/434352.html