c++methodsbisection

Finding with bisection, not stoping


I have a problem with this method, when it gets "big" array in it. When I input array with like 10 numbers it's working fine. But if I insert like 10 milion numbers or even 20 the method never end and I can't find the problem.

int bisection(int el, int* a, int n) 
{
    int i = 0;

    if (n <= 0)
    {
       return -1;
    }
    else
    {

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

     }while(i <= n);
    }
}

I have to find first number for example if I have in array:

indexs:   0 1 2 3 4 5 6 7 8  
elements: 1,1,3,3,3,5,6,7,9

And i'm looking for number 3 i have to get this as

result: (index) 2

first occurrence.


Solution

  • myusuf's answer is almost correct, but it doesn't always return the index of the first occurence. Here is my suggestion:

    int bisection(int el, int* a, int n) 
    {
        int i = 0;
        while(i < n)
        {
            // search in range i (inclusive) to n (exclusive)
            int mid = (i + n) / 2;
            if (el == a[mid] && (mid == 0 || a[mid-1] < el))
                return mid;
            if (el <= a[mid])
                 n = mid;
            else
                 i = mid + 1;
        }
        return -1;
    }