Can't find error in code for Binary search

[kingnoobcoder]

I have been trying to find what's wrong in this code for binary search. Someone please help

 #include<iostream>
using namespace std;
int binarysearch(int a[], int n, int i, int x)
{ 
   i = 0;
   int mid = (i+n)/2;
   for (i=0 ; i<n; i++)
   {
       if (a[mid]>x)
       {
        n = mid - 1;
       }
       if (a[mid] == x)
       {

           return mid ;
       }
       if (a[mid] < x)
       {
           i = mid+1 ;
       }
       mid = (i+n)/2;
    }
     if (i>n)
       {
           cout << " Element not found ";
       }

}

int main()
{
    int a[50], n, i;
    cout << "Enter the length of the array";
    cin >> n;
    cout << "Enter the sorted elements of the array";
    for (i=0; i<n ; i++)
    {
        cin >> a[i];
    }
    cout << "Enter the element to be searched";
    int x;
    cin >> x;
    int ans = binarysearch (a,n,i,x);
    cout << ans << endl;
}

[lastchance]

PLEASE, PLEASE, PLEASE USE code TAGS IF YOU WANT A RESPONSE.

What value does i have when you call your function? Answer: n

So, does your while (i<n) loop ever run? Answer: no

[kingnoobcoder]

Sorry, i had joined just yesterday, didn't know about that,
Regarding the question, if i initialise i as 0 at the start of the function and use 'for' function while initialising i as 0, i doesn't work either. I edited that in the question now. And thanks for the response :)

[salem c]

Either fill your code with debug cout statements, so you can follow the flow of your code, or use a debugger.

$ g++ -g foo.cpp
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) b binarysearch
Breakpoint 1 at 0x4009ab: file foo.cpp, line 5.
(gdb) run
Starting program: ./a.out 
Enter the length of the array5
Enter the sorted elements of the array1 3 5 7 9
Enter the element to be searched7

Breakpoint 1, binarysearch (a=0x7fffffffdd90, n=5, i=5, x=7) at foo.cpp:5
5	   i = 0;
(gdb) n
6	   int mid = (i+n)/2;
(gdb) 
7	   for (i=0 ; i<n; i++)
(gdb) 
9	       if (a[mid]>x)
(gdb) 
13	       if (a[mid] == x)
(gdb) 
18	       if (a[mid] < x)
(gdb) 
20	           i = mid+1 ;
(gdb) p i
$1 = 0
(gdb) p mid
$2 = 2
(gdb) n
22	       mid = (i+n)/2;
(gdb) p i
$3 = 3
(gdb) n
7	   for (i=0 ; i<n; i++)
(gdb) p i
$4 = 3
(gdb) n
9	       if (a[mid]>x)
(gdb) p i
$5 = 4
(gdb) 

Your SHF moment is when you start mucking about with loop control variables inside the loop itself.
> i = mid+1 ;

[lastchance]

@kingnoobcoder,

It's useful to put it in code tags, but please don't change previous postings of your code - subsequent replies become meaningless.

Now you have initialised i within the routine (and you didn't need to pass it as an argument at all, just declare it inside the routine) you can change
for (i=0 ; i<n; i++)
to
while ( i <= n )

Note that you MUST return something (e.g. -1) from your routine, even if it finds nothing.

[kingnoobcoder]

I did it, now it returns the correct answer if the element is there in the array. But if the element is not there, it still returns a position and not -1.

     #include<iostream>
using namespace std;
int binarysearch(int a[], int n, int x)
{  int i = 0;
   int mid = (i+n)/2;
   while(i<n)
   {
       if (a[mid]>x)
       {
        n = mid - 1;
       }
       if (a[mid] == x)
       {

           return mid ;
       }
       if (a[mid] < x)
       {
           i = mid+1 ;
       }
       mid = (i+n)/2;
        if (i>n)
       {
           return -1;
       }

    }
}

int main()
{
    int a[50], n, i;
    cout << "Enter the length of the array";
    cin >> n;
    cout << "Enter the sorted elements of the array";
    for (i=0; i<n ; i++)
    {
        cin >> a[i];
    }
    cout << "Enter the element to be searched";
    int x;
    cin >> x;
    int ans = binarysearch (a,n,x);
    cout << ans << endl;
}

[kingnoobcoder]

@salem c Got it but isn't taking i as mid+1/2 necessary in while loop? Replaced the for loop with while.

[lastchance]

Change
while(i<n)
to
while(i<=n)
(which was actually what I wrote in my previous post).

[kingnoobcoder]

Got it, thanks a lot mate :)