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.
Answer
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;
}