我的二进制搜索算法模板函数总是返回假

Question

所以我应该使用二进制搜索模板函数将元素从文件读取到数组，然后允许用户搜索数组中的元素。问题是每当我搜索一个数字时，即使该元素确实存在于文件中，它也会给我一个 "not found" 。我知道最好将模板函数留在头文件中，但由于我不知道如何对文件进行排序以便二分查找起作用，所以我将这些函数放在主程序中以减少混淆。认为问题出在 main() 或排序函数中，但据我所知，我无法弄清楚确切的位置以及如何修复它。

这是我的代码：

#include <iostream>
#include <string>
#include <conio.h>
#include <fstream>

using namespace std;

template<class elemType>
class orderedArrayListType
{
public:
    static const int length = 20;//Const length of array you can change it accordingly
    int list[length];
    int binarySearch(elemType const&)const;
};

template<class elemType>
int orderedArrayListType<elemType>::binarySearch(const elemType& item) const
{
    int first = 0;
    int last = length - 1;
    int mid;

    bool found = false;

    while (first <= last && !found)
    {
        mid = (first + last) / 2;

        if (list[mid] == item)
            found = true;
        else if (list[mid] > item)
            last = mid - 1;
        else
            first = mid + 1;
    }

    if (found)
        return mid;
    else
        return -1;
}

void main()
{
    std::fstream numberFile("text.txt", std::ios_base::in);

    orderedArrayListType<int> object;

    int number=0, a;
    int i = 0;
    int numberToSearch;

    while (numberFile >> a)
    {
        object.list[i] = number;//Initalizing the array
        i++;
    }

    cout << "Enter Number you want to search" << endl;
    cin >> numberToSearch;

    int output = object.binarySearch(numberToSearch);//Make search

    if (output>0)
    {
        cout << "Element found at Index: " << output << endl;
    }
    else
    {
        cout << "Element not Found" << endl;
    }



}

这些是 text.txt 文件的内容：

1 2 3 4 5 6 7 8 9 10

提前致谢！

Answer 1

此处您将列表的所有元素设置为 0:

while (numberFile >> a)
{
    object.list[i] = number;//Initalizing the array
    i++;
}

相反，您应该填写从文件中读取的数字：

while (numberFile >> a)
{
    object.list[i] = a;//Initalizing the array
    i++;
}

那么，如果您对列表使用模板参数会更好，否则模板将只适用于 int:

template<typename elemType>
class orderedArrayListType
{
public:
    static const int length = 20;//Const length of array you can change it accordingly
    elemType list[length];
    int binarySearch(elemType const&)const;
};

template<typename elemType>
int orderedArrayListType<elemType>::binarySearch(const elemType& item) const
{
    int first = 0;
    int last = length - 1;
    elemType mid;
    ....

Answer 2

问题不在二进制搜索函数中，而是在：

 while (numberFile >> a)
 {
    object.list[i] = number;//Initalizing the array
    i++;
 }

number 始终为 0。

一个建议，更改：

mid = (first + last) / 2;

到

mid=first + (last-first)/2

避免溢出。寻找这些情况也是一个很好的编程习惯。

Answer 3

多亏了这些提示，我才能够正确运行程序。这是经过编辑的 main() 程序代码，可以让任何可能偶然发现此类程序问题的人更加清楚。

void main()
{
    std::fstream numberFile("text.txt", std::ios_base::in);

    orderedArrayListType<int> object;

    int number=0, a;
    int i = 0;
    int numberToSearch;

    while (numberFile >> a)
    {
        object.list[i] = a;//Initalizing the array
        i++;
    }

    cout << "Enter Number you want to search" << endl;
    cin >> numberToSearch;

    int output = object.binarySearch(numberToSearch);//Make search

    if (output>0)
    {
        cout << "Element found at Index: " << output << endl;
    }
    else
    {
        cout << "Element not Found" << endl;
    }



}

请注意，仅根据用户 (alain) 的建议对数组初始化的部分进行了更改：

while (numberFile >> a)
    {
        object.list[i] = a;//Initalizing the array
        i++;
    }

我的二进制搜索算法模板函数总是返回假

My Binary Search Algorithm Template Function is Always Returning False

c++

arrays

algorithm

binary-search

readfile