Бинарный поиск с использованием вектора

Question

Итак. Я уже узнал о бинарном поиске и о том, как он работает, и даже попробовал его, используя постоянный массив без какого-либо ввода от пользователя, но теперь я пытаюсь применить вектор вместо массива, чтобы пользователь вводил значения обоих список, в котором нужно искать числа из vector и цель для поиска. Здесь я использовал обычный метод «разделяй и властвуй» при использовании массива

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;
}

Моя проблема в том, что я использовал почти такой же метод, используя вектор, но он показывает либо бесконечное количество ** Ваш результат найден в индексе : ** (номер неверного индекса). Или это не показывает никакого результата вообще или даже показывает, что результат не найден, отличается каждый раз как-то. Вот при использовании вектора

#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;, Может быть, речь идет о том, как использовать размер векторов? Может ли кто-нибудь просветить меня до этого

Answer 1

проблем:

1. нет возврата. добавить

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

идет слишком быстро, может пропустить некоторые числа

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

почему слишком быстрое может быть проблемой? попробуй когда

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

Answer 2

Вам нужно return mean после этой строки

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

Точно так же, как вы делаете в версии массива.

Кроме того, как упоминалось в комментариях, это будет работать, только если пользователь вводит в отсортированные данные.

Answer 3

Ну, другие ответы помогли решить проблему, но если вы не знали, есть встроенные функции для выполнения двоичного поиска в C++, которые вы можете использовать.

Я перечислю функции связанный бинарный поиск:

• sort : вы можете использовать бинарный поиск только в отсортированном данных, поэтому перед поиском необходимо убедиться, что данные отсортированы.
• lower_bound : эта функция возвращает итератор первому элементу больше или равно значению.
• upper_bound : эта функция возвращает итератор первому элементу, который на больше value.
• 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";
    }

}