Сортировка затем поиск (векторы с ++)

Question

Я уже пробовал искать в одиночку, используя векторы вместо массивов с фиксированной памятью, и это работало на отлично. Но теперь, когда я пытаюсь сначала отсортировать вектор , чтобы он работал в двоичном поиске , программа останавливается после того, как пользователь вводит список векторов. Вот код

#include <iostream>
#include <vector>
using namespace std;
void BubbleSort(vector<int>list){
    int temp;
    for (int i=0;i<list.size();i++){
        for (int j=1;j<list.size();j++){
            if(list[i]>list[j]){
                list[i]=temp;
                list[j]=list[i];
                temp=list[j];
            }
        }
    }
}
int Binary_search(vector<int>list,int target){
    int maximum=(list.size())-1;
    int minimum = 0;
    int mean;
    while (maximum>minimum){
        mean = (maximum+minimum)/2;
        if (list[mean] == target){
            cout << "The number you're looking for is found! \n";
            return mean;
        }
        else if(list[mean] > target){
            maximum = mean;
        }
        else{
            minimum = mean;
        }
    }
    return -1;
}
int main()
{
    unsigned int k;
    int x,a,target;
    vector<int>list;
    cout << "Enter the amount of numbers you want to enlist \n";
    cin >> k;
    while((list.size()< k) && (cin >> x)){
        list.push_back(a);
    }
    BubbleSort(list);
    cout << "Enter the target that you want to search for \n";
    cin >> target;
    int result = Binary_search(list,target);
    if(result == -1){
        cout << "Your result is not found ";
    }
    else{
        cout << "Your result is found at the index: " << result;
    }
    return 0;
}

Я ожидаю программа для сортировки (но не для распечатки отсортированного вектора, просто для сортировки сзади, а затем показывать результат в конце после поиска) Проблема, конечно же, в части сортировки, но я не знаю, можно ли использовать Bubble Sort до это, кто-нибудь может указать мне правильный способ сортировки, а затем искать?

Answer 1

@ Oliver_Queen есть некоторые проблемы в вашем коде, но если вы будете следовать комментариям @ 1201ProgramAlarm и @Blastfurnace, вы можете частично решить вашу проблему, но в функции Binary_search () вы должны использовать mean-1 или mean+1 для maximum и minimum соответственно и проверьте, верно ли условие в конце, вот ваш фиксированный код:

void BubbleSort(vector<int> &list){
    int temp;
    for (int i=0;i<list.size();i++){
        for (int j=i+1;j<list.size();j++){
            if(list[i]>list[j]){
                temp=list[i];
                list[i]=list[j];
                list[j]=temp;
            }
        }
    }
}

и в функции Binary_search() как:

int Binary_search(vector<int>list,int target){
    int maximum=(list.size())-1;
    int minimum = 0;
    int mean;
    while (maximum>minimum){
        mean = (maximum+minimum)/2;
        if (list[mean] == target){
            cout << "The number you're looking for is found! \n";
            return mean;
        }
        else if(list[mean] > target){
            maximum = mean-1;
        }
        else{
            minimum = mean+1;
        }
    }
    if (list[minimum] == target) return minimum;
    return -1;
}

или для исключения условного выражения после цикло while:

int Binary_search(vector<int>list,int target){
    int maximum=(list.size())-1, minimum = 0, mean;
    while (minimum <= maximum){
        mean = (maximum+minimum)/2;
        if (list[mean] == target)    return mean;
        else if(list[mean] > target) maximum = mean-1;
        else                         minimum = mean+1;
    }
    return -1;
}

Но я рекомендую вам использовать std::sort() из библиотеки алгоритмов для выполнения сортировки в O(N*log(N)) где N - количество элементов для сортировки, и используйте std::binary_search, чтобы проверить, принадлежит ли он, или std::lower_bound, чтобы найти первый элемент не меньше указанного значения .

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

using namespace std;

int main()
{
    unsigned int k;
    int x,a,target;
    vector<int>list;
    cout << "Enter the amount of numbers you want to enlist \n";
    cin >> k;
    while((list.size()< k) && (cin >> x)){
        list.push_back(x);
    }
    sort(list.begin(), list.end());
    cout << "Enter the target that you want to search for \n";
    cin >> target;
    auto result = lower_bound(list.begin(), list.end(), target);
    if(result == list.end()){
        cout << "Your result is not found ";
    }
    else{
        cout << "Your result is found at the index: " << result-list.begin();
    }
    return 0;
}