zkazemi90
BAN USERTo get O(lgn), we need to find the lower and upper bound of the given number in the array.
int findnum(int arr[], int n, int k)
{
int start=0;
int end = n-1;
int med=-1;
int low= 0;
int hi = 0;
while(start <= end)
{
med = (start+end)/2;
if( arr[med] < k)
{
low=med;
start = med+1;
}
else if(arr[med] >= k)
end=med-1;
}
start=0;
end = n-1;
while(start <= end)
{
med = (start+end)/2;
if(arr[med] > k)
{
hi = med;
end=med-1;
}
else if(arr[med] <= k)
start = med+1;
}
if(hi == 0 && low != 0)
{
return (n-low-1);
}
else if (low == 0 && hi !=0 )
return hi-low;
else if( hi == 0 && low == 0)
{
if(arr[low] == k)
return n;
return 0;
}
else
return hi-low-1;
first partition the array where the left side has 0 remainders, and the right side 1, 2; in the next step partition the remainder where left side of the remainder of the array (middle of array) is 1 and right side is 2.
- zkazemi90 June 12, 2015