Binary seach not working for a particular output

Question

Getting unexpected output just for a single input in binary search. When I enter {1,2,3,4,5} as input in array in binary search program then it shows element not present for only the input'2' even when element is present. Trying on codeblocks.

I have tried tracing the code in iteration and I don't understand why is this not working and if the variable (pos is my case) value is changing or not.

#include <iostream>
using namespace std;

int main()
{
    int last,fin,beg=0,mid,pos=-1,i,*a;

    cout<<"Enter the size of array: ";
    cin>>last;

    a=new int[last];

    cout<<"Enter the elements in array"<<endl;
    for(i=0;i<last;i++)
    {
        cin>>a[i];                            
    }

    cout<<endl<<"Enter the element you want to find: ";
    cin>>fin;

    for(i=beg;i<=last;i++)
    {

        mid=(beg+last)/2;

        if(a[mid]==fin)
        {
            pos=mid;
        }
        else if(a[mid]>fin)
        {
            last=mid-1;
        }
        else
        {
            beg=mid+1;
        }
    }

    if(pos==-1)
    {
        cout<<"Element not present in array"<<endl;
    }
    else
    {
        cout<<"element found "<<fin<<" at "<<pos+1<<" position"<<endl;
    }

    delete a;
    return 0;
}

I expect that output of 2 should be : element found 2 at 2 position when I enter size (variable last) as 5 and elements as 1,2,3,4,5 . I am getting output : Element not present in array.

Answer 1

Change your loop to this:

while (beg <= last) {
    int mid = (beg + last) / 2;
    if (a[mid] == fin) {
        pos = mid;
        break;              // break where you find the element in the array
    }
    else if (a[mid] > fin) last = mid - 1;
    else beg = mid + 1;
}

Your loop is incorrect. You are changing the bounds for searching in the loop (beg and last). So, to check if you can't search any further, you need to check whether beg has crossed last in which case, you will stop the search.

Also, in your code, a is an array allocated using new, but you are calling delete a instead of delete[] a.