Logic of binary search

Question

I read a Pseudo Code of binary search in a data structure book and then I started to writing code. the code that i written is :

#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;
 }

there is no any Error but a logic fault is there . it just return 0 value from BSearch function and i just get this message "Item NOT Exist". where is my bug ?! i didn't find it. Thanks

• Carl Norum: What happened when you stepped though your code with a debugger?
• John Martin: @irrelephant: In the book the writer said "last <- loc -1"
• Jonathan Leffler: Note that in Section 6.2.1 of Sorting and Searching, Knuth documents that the first binary search routine was published in 1946, but the first published binary search routine without bugs did not appear until 1962. It is surprisingly hard to get binary search right!
• Jonathan Leffler: Also, it is nasty to make the user type in a large number of values, only to allow just one search on them. You should really add a loop around the 'Enter item to search for' code so that you can do thorough testing on a single set of data.
• John Martin: @ Jonathan Leffler:Thank you

Answer 1

The binary search only works for ordered lists. But you don't order the list you get from std::cin, therefore you get wrong results from your binary search.

To fix this you either have to restrict the input to pre-ordered lists, or you have to initially order your list before doing the binary search.

• John Martin: may you help me to write a Binary code that works for Unordered lists ?
• Karthik T: @JohnMartin - The only Binary search algorithm which works on unordered lists is one that sorts it before searching.
• Haatschii: @JohnMartin What Karthik T says is true. So if it is a homework you should read the instruction again, if you can take a sorted list for granted. I would wonder if not, because effeciently sorting a list is way more work than a binary search. If you indeed need it for some programm of yours I would recomend you to use the standard library algorithms. Espacially en.cppreference.com/w/cpp/algorithm/find and en.cppreference.com/w/cpp/algorithm/sort may help.

Answer 2

I tried your code out and it seems to work ok. You've got to remember that that the numbers you enter must be ordered from small to big.

Answer 3

Binary Search involves reducing the search range to half by dividing the range into half of its original size. Binary Search operates upon sorted array. It compares the element at the mid of this range with the value to be searched, if the value is smaller than the mid value, then the value is looked up in the range from first element to mid, otherwise the new search range becomes mid to last element. This process continues until the required element is located or lower bound becomes greater than upper bound. Efficiency of Binary Search is O(log2n) in average and worst case and is O(1) in best case. The ‘C’ program to perform Binary Search is given below:

/* 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...!");
}