Проблема с бинарной функцией поиска

Question

Проблема с бинарной функцией поиска

Независимо от того, какое значение я ищу, программа говорит, что оно не найдено в файле. Я не могу понять, что не так с моим кодом.

     int main()
{
int array1[MAX_NUMBER];
int length;
int number;
int location;

input (array1, MAX_NUMBER, length);

cout<<"Please enter a number to search for:"<<endl;
cin>>number;

location=search(array1, length, number);

if (location!=-1)
{
cout<<"The number "<<number<<" was found in the "<<location<<" position."<<endl;
}

else
{
cout<<"The number "<<number<<" was not found in the file."<<endl;
}return 0;
}

void input(int a[], int size, int& number_used)
{
ifstream infile;
int input;

infile.open("numbers.txt");

if (infile.fail())
{
cout<<"Input file opening failed."<<endl;
exit(1);
}

int i;for (i=0; i<=size; i++)
{
while (infile>>input)
{

a[i]=input;
cout<<a[i]<<endl;

}
}

number_used=i;

}

int search(const int a[], int number_used, int search_value)
{
int start=1;
int end=number_used;
int key=search_value;

while (start<=end)
{
int mid=((start+end)/2);

if (a[mid]==key)
{
return mid;
}

if (a[mid]>key)
{
end=mid-1;
}

else
{
start=mid+1;
}

}
return -1;}

Моя проблема в основном коде или в функции поиска?

Входной файл:

Например, при вводе 19 выдается «Число 19 не найдено в файле».

-2

binary-search c++

Решение

Другие решения

Вы не вычисляете длину списка значений, которые вы прочитали правильно. У вас есть цикл внутри цикла, и он делает что-то странное.

То, что вы должны делать, это что-то вроде:

int i;

while (i < size && infile >> input)
{
a[i]=input;
cout<<a[i]<<endl;
i++;
}

number_used=i;

1

Бинарный поиск требует, чтобы массив уже был отсортирован. Попробуйте свой алгоритм вручную: найдите число 4 в [4, 1, 3, 6, 5]. 4 больше среднего элемента, поэтому алгоритм перейдет к части [4, 6, 5] массива.

0

Источник

Accepted Answer

Вы не заполняете массив правильно в функции input,
Вы должны использовать другой индекс для хранения значений в массиве, в противном случае i не будет указывать действительный и значимый индекс в a :

int k = 0; // <--------------------------

int i;
for (i = 0; i <= size; i++)
{
while (infile >> input && k < size)
{

a[k] = input; // <----------------

k++;  // <----------------
}
}

number_used = k; // <-------------

И, как прокомментировал WhozCraig, вы должны знать, что массивы начинаются с 0 не 1 поэтому в search метод:

int start = 0;

2