using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound ub.
Now -
initially lb = 0, ub = 1;
while (a[ub] < k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar <[email protected]> wrote:
> @Ankur Don't think there's any major reason for using powers of 2 except
> the fact that computing the powers of 2 can be done very efficiently than
> computing the powers of any other number. Complexity in any case remains the
> same.
>
>
> On 24 October 2011 10:29, rahul sharma <[email protected]> wrote:
>
>> +1 ankur
>>
>>
>> On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg <[email protected]> wrote:
>>
>>> Use Binary Search
>>>
>>> start = 2^n-1 high =2^n where n=0,1....
>>>
>>> On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal <[email protected]
>>> > wrote:
>>>
>>>> hint 1: try to find 2 indexes i, j such that a[i] <= K <= a[j]
>>>>
>>>>
>>>> On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta <[email protected]>wrote:
>>>>
>>>>> Given a sorted array of Infinite size, find an element âKâ in the
>>>>> array without using extra memory in O (lgn) time
>>>>>
>>>>> --
>>>>> 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?hl=en.
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Sunny Aggrawal
>>>> B.Tech. V year,CSI
>>>> Indian Institute Of Technology,Roorkee
>>>>
>>>>
>>>> --
>>>> 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?hl=en.
>>>>
>>>
>>> --
>>> 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?hl=en.
>>>
>>
>> --
>> 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?hl=en.
>>
>
>
>
> --
> Bittu Sarkar
> 5th Year Dual Degree Student
> Department of Computer Science & Engineering
> Indian Institute of Technology Kharagpur
>
>
> --
> 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?hl=en.
>
--
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?hl=en.
