Логика бинарного поиска

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

#include <iostream.h>
#include <conio.h>
template <class T>

int BSearch(T x[], const int n, T item)
{
int loc, first = 0, found = 0, last = n-1;
while(first <= last && !found)
{
loc = (first + last)/2;
if(item < x[loc])
last = loc - 1;
else if(item > x[loc])
first = loc + 1;
else
found = 1;
}
return found;
}

int main()
{
const int n =5;
int x[n],item;
cout << "Pls enter " <<n<<" number(s): ";

for(int i = 0; i < n;i++)
cin >> x[i];
cout << "Pls enter the item to Search: ";
cin >> item;
if(BSearch(x,n,item))
cout << "\n\t Item Exist";
else
cout << "\n\t Item NOT Exist";

getch();
return 0;
}

Нет ошибки, но есть логическая ошибка. он просто возвращает значение 0 из функции BSearch, и я просто получаю это сообщение «Item NOT Exist». где моя ошибка ?! Я не нашел это.
Спасибо

3

Решение

Бинарный поиск работает только для упорядоченных списков. Но вы не заказываете список, который вы получаете от std::cinпоэтому вы получаете неверные результаты вашего бинарного поиска.

Чтобы это исправить, вы должны либо ограничить ввод предварительно упорядоченными списками, либо сначала упорядочить свой список перед выполнением бинарного поиска.

8

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

Я попробовал ваш код, и, кажется, он работает нормально. Вы должны помнить, что числа, которые вы вводите, должны быть упорядочены от маленького к большому.

4

Бинарный поиск включает в себя уменьшение диапазона поиска до половины путем деления диапазона на половину его исходного размера. Бинарный поиск работает с отсортированным массивом. Он сравнивает элемент в середине этого диапазона с искомым значением, если значение меньше среднего значения, то значение ищется в диапазоне от первого элемента до середины, в противном случае новый диапазон поиска становится средним до последний элемент. Этот процесс продолжается до тех пор, пока требуемый элемент не будет найден или нижняя граница не станет больше верхней границы. Эффективность бинарного поиска составляет O (log2n) в среднем и наихудшем случае и O (1) в лучшем случае. Программа «C» для выполнения бинарного поиска приведена ниже:

/* Binary Search */
#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],i,n,val;
int lb,ub,mid;
printf(“nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“nEnter the value to search?”);
scanf(“%d”,&val);
lb=0;ub=n-1;
while(lb<=ub){
mid=(lb+ub)/2;
if(val<arr[mid])
ub = mid-1;
else if(val>arr[mid])
lb = mid+1;
else {
printf(“nNumber found…!”);
return;
}
}
printf(“nNumber not found…!”);
}
0