Binary Search in C++ using old code, search doesnt register element in last position

[karmanya]

hey,
Using old code(non-ANSI)
The search detects elements in all positions in the 1-d array, except the last one
pastebin- *pastebin.com/f4db70a8b

//program to run binary search
#include <iostream.h>
int main ()
{
int a[10],n,x,pos=-1,i,first,last,mid;
cout<<" Enter the number of elements into the array ";
cin>>n;
for(i=0;i<n;++i)
{
cout<<"\n Enter element number "<<i+1<<" ";
cin>>a;
}
cout<<"Enter the number to be searched \t";
cin>>x;
first=0;
last=n-1;
while((first<=last)&&(pos==-1))
{
mid=(first+last)/2;
if(a[mid]==x)
pos=mid;
else
last=mid-1;
}
if(pos==-1)
cout<<" \t Element not found ";
else
cout<<" Element found at position "<<pos+1;
return 0;
}

Does anyone see my mistake? debugging is not my strong suit

 

[red_devil]

Re: Binary Search in C++ using old code, search doesnt register element in last posi

#include <iostream.h>
int main ()
{
int a[10],n,x,pos=-1,i,first,last,mid;
cout<<" Enter the number of elements into the array ";
cin>>n;
for(i=0;i<n;++i)
{
cout<<"\n Enter element number "<<i+1<<" ";
cin>>a;
}
cout<<"Enter the number to be searched \t";
cin>>x;
first=0;
last=n-1;
while((first<=last)&&(pos==-1))
{
mid=(first+last)/2;
if(a[mid]==x)
pos=mid;
else
last=mid-1;
}
if(pos==-1)
cout<<" \t Element not found ";
else
cout<<" Element found at position "<<pos+1;
return 0;
}

AFAIK, the logic is wrong mate...

Binary search should divide the array of elements into 2 and then find out which half the element is likely to be found..{assuming the array is sorted } and then narrow the search down to that particular half ...

the code you've posted doesn't do that..

it should be something like :



if ( element to be searched ) < the middle element,
then search the array from first element to an element before middle element
else
search the array from the element after the middle element to the last element


all this should be done within a conditional loop, ofcourse.

PS : it was soo tempting to write the code itself... but i guess you'd want to do it on your own ...

 

[dheeraj_kumar]

Re: Binary Search in C++ using old code, search doesnt register element in last posi

Here, I'll write a pseudocode, I prefer it as a function due to recursive calling, returns array index if found, -1 if not.

int binsearch (int a[], int start = 0, int end = sizeof(a)/sizeof(int), int searchelement)
{
   mid = (start + end) / 2;
   if (a[mid] == searchelement) //bingo, got it
      return mid;
   else if ((a[mid] > searchelement) && (mid != start)) //to prevent infinite loops
      return binsearch (a[], start, mid, searchelement);
   else if ((a[mid] < searchelement) && (mid != start)) //to prevent infinite loops
      return binsearch (a[], mid, end, searchelement);
   else //to actually exit from the function
      return -1;
}

 

[karmanya]

Re: Binary Search in C++ using old code, search doesnt register element in last posi

Thanks guys, Thanks to QwertyM who helped me fix it.
last=mid instead of mid-1 fixed it.