I guess the Soln given is O(n)
Much better can be achieved through binary serach O(nlogn)
int binsearch(int a[],int start,int end,int key)
{
int mid=(start+end)/2;
if(start==end && a[mid]!=key)
return -1;
if(a[mid]>key)
end=mid;
else if(a[mid]<key)
start=mid;
else
return mid;
}
int search(int a[],int key,int n)
{
int p=binsearch(a,0,n,key)
if(p>=0)
while(a[p]==key)
p++;
return p-1;
}
On Sun, Mar 1, 2009 at 3:14 PM, Miroslav Balaz <[email protected]> wrote:
>
> cout << ((int)((int*)upperbound(a,a+5,k)-a))/4-1;
>
> 2009/3/1 sharad kumar <[email protected]>
>>
>> #include<iostream.h>
>> int main()
>> {
>> int a[5]={3,3,3,6,7};
>> int k;
>> cin>>k;
>> int i=0,j=1,c=0;
>> for(;i<5;i++)
>> {
>> if(a[j-1]!=a[i]&& a[i]!=k)
>> j++;
>> else
>> c=i;
>> }
>> cout<<c;
>> return 0;
>> }
>>
>> On Sun, Mar 1, 2009 at 9:50 AM, sharad kumar <[email protected]>
>> wrote:
>>>
>>> hi,
>>> does the above solution need any time complexity and space complexity in
>>> specifific. idont understand use binary search
>>> On Sun, Mar 1, 2009 at 12:13 AM, jaanu <[email protected]> wrote:
>>>>
>>>> Given a sorted arrays of N integers, possibly with duplicates, write a
>>>> function that
>>>> returns the highest index of an element X in that array if found or -1
>>>> otherwise.(use Binary search)
>>>>
>>>>
>>>
>>
>>
>>
>
>
> >
>
--
Prakhar
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
