利用向量实现的二分查找

Question

所以...我已经学习了二分查找以及它的工作原理，并尝试在没有用户输入的情况下使用常量数组进行操作，但现在我正在尝试使用向量而不是数组来让用户输入要从中搜索数字的列表，以及要搜索的目标。在这里，我使用了普通的分治算法来处理数组。

using namespace std;
int Binary_search(int x[],int size,int target){
    int maximum= size-1;
    int minimum = 0;
    int mean;
    while (maximum>minimum){
        mean = (maximum+minimum)/2;
        if (x[mean] == target){
            cout << "The number you're looking for is found! \n";
            return mean;
        }
        else if(x[mean] > target){
            maximum = (mean-1);
        }
        else{
            minimum = (mean+1);
        }
    }
    return -1;
}
int main(){
    int x[]={1,2,3,4,5};
    int a=sizeof(x)/sizeof(x[0]);
    int target=4;
    int show=Binary_search(x,a,target);
    if (show != -1){
        cout << "Your result is in the index: " << show;
    }
    return 0;
}

我的问题是，我用vector编写了几乎相同的方法，但它要么显示出无限数量的“您的结果位于索引：”（错误索引数），要么根本不显示任何结果，甚至显示未找到结果，每次都有所不同。以下是使用vector时的代码：

#include <iostream>
#include <vector>
using namespace std;
int Binary_search(vector<int>x,int target){
    int maximum=(x.size())-1;
    int minimum = 0;
    int mean;
    while (maximum>minimum){
        mean = (maximum+minimum)/2;
        if (x[mean] == target){
            cout << "The number you're looking for is found! \n";
        }
        else if(x[mean] > target){
            maximum = (mean-1);
        }
        else{
            minimum = (mean+1);
        }
    }
    return -1;
}
int main(){
    unsigned int i;
    int n;
    vector<int>x;
    cout << "Enter the amount of numbers you want to evaluate: ";
    cin >> i;
    cout << "Enter your numbers to be evaluated: " << endl;
    while (x.size() < i && cin >> n){
        x.push_back(n);
    }
    int target;
    cout << "Enter the target you want to search for in the selected array \n";
    cin >> target;
    int show = Binary_search(x,target);
    if (show == -1){
        cout << "Your result is not found ! ";
    }
    else{
        cout << "Your result is in the index: " << show;
    }
    return 0;
}

我认为问题出在这部分代码 int maximum=(x.size())-1; ，也许与如何使用向量的大小有关？能否有人给我解惑一下？

- user12975434

---

你有没有考虑过，可能你的数组版本一直存在问题，而使用“vector”检测到了故障？其次，为什么不像数组版本那样将数据硬编码到向量中进行测试呢？ - PaulMcKenzie

请注意，二分查找仅适用于已排序的数据集。如果用户输入未排序的数据，则需要在运行二分查找之前对向量进行排序。 - NathanOliver

好的，注意到了。谢谢！NathanOliver 我不太理解您所说的“一直是坏的”，能请您解释一下吗？@PaulMcKenzie - user12975434

有时候使用数组会隐藏掉一个偏移量为一或其他微妙的错误。当使用向量时，程序的行为可能会有所不同，其中隐藏的错误现在被暴露了。 - PaulMcKenzie

Answer 1

其他的回答已经帮助解决了这个问题，但是如果您不知道，C++ 中有内置函数可以执行二分搜索 ，您可以使用它们。

我将列出与二分搜索相关的 函数:

• sort：你只能在已排序的数据上使用二分搜索，所以在搜索之前，必须保证数据已排序。
• lower_bound：此函数返回一个迭代器，指向第一个大于或等于值的元素。
• upper_bound：此函数返回一个迭代器，指向第一个大于值的元素。
• binary_search：此函数返回一个布尔值，表示是否找到该值（与您的程序完全相同）。

以下是演示上述函数的代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>

typedef std::vector<int>::iterator iter;

int main() {

    std::vector<int> vec = {10, 20, 30, 30, 20, 10, 10, 20};

    // sort the data
    // the data will be:
    // 10, 10, 10, 20, 20, 20, 30, 30
    std::sort(vec.begin(), vec.end());

    // index of the first element, greater than or equal to 20
    iter low = std::lower_bound(vec.begin(), vec.end(), 20);

    // index of the first element, greater than 20
    iter high = std::upper_bound(vec.begin(), vec.end(), 20);

    std::cout << "index of first element, greater than or equal to 20 is: " << (low - vec.begin()) << '\n';

    std::cout << "index of first element, greater than to 20 is: " << (high - vec.begin()) << '\n';

    // classic binary search
    // check whether a givin value exists in the array or not
    if (std::binary_search(vec.begin(), vec.end(), 99)) {
        std::cout << "Found\n";
    } else {
        std::cout << "Not found\n";
    }

}

- Reslan Tinawi

---

谢谢！但这肯定包括一个预定义的算法，对吧？ - user12975434

很抱歉，我没有清楚理解你的问题。 如果你的意思是在开始时定义预设算法并实现，那么答案是否定的。 这些是内置函数，你可以立即使用它们。 - Reslan Tinawi

Answer 2

在这行代码后面，你需要返回平均值

cout << "The number you're looking for is found! \n";

就像在数组版本中所做的那样。

另外，正如评论中提到的，这只适用于用户输入排序数据的情况。

- Lou Franco

Answer 3

问题：

1. 没有返回值。添加

cout << "The number you're looking for is found! \n";
return mean;

2. 速度过快可能会跳过一些数字

else if(x[mean] > target)
{
    maximum = mean;
}
else
{
    minimum = mean;
}

为什么速度过快可能会成为问题？ 尝试时。

vector<int>x{1,2,3,4,5,6};
int target = 4;

- Austin Jiang