c++ - 二分查找函数的问题

Question

顶部列出的 binary_search 函数有问题。不确定去哪里。我对二进制搜索不是很熟悉。

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

void get_input(ifstream& fin, int a[], int size, int & array_size);

void binary_search (int a[], int & array_size)
{
    cout << "Please enter the element you would like to search for \n";
    int element;
    cin >> element;

    int lastindex=array_size-1, startindex=0;

    while (startindex <= lastindex)
    {
        int midindex=(array_size/2);
        if(element > a[midindex])
        {
            startindex=midindex;
        }
        else if (element < a[midindex])
        {
            lastindex=midindex-1;
        }

    }

}

int main()
{
    int array_size=-1;
    int a[100];

    ifstream fin;

    get_input (fin, a, 100, array_size);

    binary_search (a, array_size);

    return 0;
}

void get_input (ifstream& fin, int a[], int size, int & array_size)
{
    fin.open("numbers.txt");
    if (fin.fail())
    {
        cout << "File failed to open";
        exit(1);
    }


    for(int i = 0; i < size; i++)
    {
        a[i] = 0;
    }

    cout << "The numbers in the array are: \n\n";

    for (int i = 0; i < size; i++)
    {
        if (!fin.eof())
        {
            fin >> a[i];
            array_size ++;
        }
    }

    for (int i = 0; i < array_size; i++)
    {
            cout << a[i] << "  ";
    }

    cout << "\n\n\n";
    cout << "The numbers in the array sorted are: \n\n";

   for(int i = 0; i < array_size; ++i )
   {
        int temp2 = a[i];

        for (int j = i+1; j < array_size; ++j )
        {

            if( a[j] < temp2)
            {
                temp2 = a[j];

                int temp = a[i];
                a[i]    = a[j];
                a[j]    = temp;
            }
        }
    }





    for (int i = 0; i < array_size; i++)
    {
            cout << a[i] << "  ";
    }

    cout << "\n\n\n";

    fin.close();
}

完成后，程序假设从文件中获取输入并将其分配给数组，然后对数组进行排序。在此之后，我需要使用二进制搜索来查找用户给出的数字并将其在数组中的位置显示给用户。

更新:找到的索引输出错误....我应该只向 midindex 添加一个吗？

void binary_search (int a[], int & array_size)
{
    cout << "Please enter the element you would like to search for \n";
    int element;
    cin >> element;

    int lastindex=array_size-1, startindex=0;

    while (startindex <= lastindex)
    {
        int midindex= startindex + (lastindex - startindex) / 2;

        if(element > a[midindex])
        {
            startindex=midindex+1;
        }
        else if (element < a[midindex])
        {
            lastindex=midindex-1;
        }
        else if (element == a[midindex])
        {
            cout<<"Element "<<element<<" found at index "<<midindex<<endl;
            return;
        }



    }

}

Answer 1

尝试改变

startindex=midindex;

到:

startindex=midindex + 1;

和

int midindex=(array_size/2);

到

int midindex= startindex + (lastindex - startindex) / 2

最重要的是，当您找到元素时，您什么都不做!!

if(element == a[midindex]) {
  cout<<"Element "<<element<<" found at index "<<midindex<<endl;
  return;
}