Re: [algogeeks] Search an element in an Infinite array
@Saurabh There is no biggest number in an infinite array [?]
On 25 October 2011 09:07, saurabh singh saurab...@gmail.com wrote:
suppose the element doesn't lies in the array and is bigger than the
biggest number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel
ravindra.it...@gmail.comwrote:
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 bittu...@gmail.com 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 rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
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
sunny816.i...@gmail.com 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 ankuj2...@gmail.comwrote:
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
329.gif
Re: [algogeeks] Search an element in an Infinite array
Really?
the array is infinite length..
what if the sequence is 1,1,1,1,1,1,1,1...infinity?
We need to know the max in order the algorithm is terminating..
On Tue, Oct 25, 2011 at 11:32 AM, Bittu Sarkar bittu...@gmail.com wrote:
@Saurabh There is no biggest number in an infinite array [?]
On 25 October 2011 09:07, saurabh singh saurab...@gmail.com wrote:
suppose the element doesn't lies in the array and is bigger than the
biggest number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel ravindra.it...@gmail.com
wrote:
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 bittu...@gmail.comwrote:
@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 rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
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
sunny816.i...@gmail.com 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
ankuj2...@gmail.comwrote:
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For
Re: [algogeeks] Search an element in an Infinite array
@Saurabh I think you did not get the question clearly. It's
a theoretical question because in practice you cannot have an infinite
length array of non-decreasing numbers anyways. Yes the sequence 1,1,1,...
is infinite and the algorithm cannot just know all by itself what the
largest number is, just because it has processed millions of 1s. In this
case no algorithm can find the required number (1) in which case the
algorithm does not terminate.
On 25 October 2011 13:46, saurabh singh saurab...@gmail.com wrote:
Really?
the array is infinite length..
what if the sequence is 1,1,1,1,1,1,1,1...infinity?
We need to know the max in order the algorithm is terminating..
On Tue, Oct 25, 2011 at 11:32 AM, Bittu Sarkar bittu...@gmail.com wrote:
@Saurabh There is no biggest number in an infinite array [?]
On 25 October 2011 09:07, saurabh singh saurab...@gmail.com wrote:
suppose the element doesn't lies in the array and is bigger than the
biggest number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel
ravindra.it...@gmail.com wrote:
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 bittu...@gmail.comwrote:
@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 rahul23111...@gmail.comwrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
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
sunny816.i...@gmail.com 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
ankuj2...@gmail.comwrote:
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] Search an element in an Infinite array
yeah...first search in 2^0 and 2^1if elemtn range is between this thern
search in this length with Binary search else
searchin 2^1 and 1^2 and apply same procedure until element range is found
and if element is not found in range then it means element not found
On Tue, Oct 25, 2011 at 3:12 PM, Bittu Sarkar bittu...@gmail.com wrote:
@Saurabh I think you did not get the question clearly. It's
a theoretical question because in practice you cannot have an infinite
length array of non-decreasing numbers anyways. Yes the sequence 1,1,1,...
is infinite and the algorithm cannot just know all by itself what the
largest number is, just because it has processed millions of 1s. In this
case no algorithm can find the required number (1) in which case the
algorithm does not terminate.
On 25 October 2011 13:46, saurabh singh saurab...@gmail.com wrote:
Really?
the array is infinite length..
what if the sequence is
1,1,1,1,1,1,1,1...infinity?
We need to know the max in order the algorithm is terminating..
On Tue, Oct 25, 2011 at 11:32 AM, Bittu Sarkar bittu...@gmail.comwrote:
@Saurabh There is no biggest number in an infinite array [?]
On 25 October 2011 09:07, saurabh singh saurab...@gmail.com wrote:
suppose the element doesn't lies in the array and is bigger than the
biggest number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel
ravindra.it...@gmail.com wrote:
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 bittu...@gmail.comwrote:
@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 rahul23111...@gmail.comwrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
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
sunny816.i...@gmail.com 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 ankuj2...@gmail.com
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this
Re: [algogeeks] Search an element in an Infinite array
@sharmila...wat r u saying??cant get u? On Tue, Oct 25, 2011 at 4:57 PM, sharmila saru sharmi99p...@gmail.comwrote: Give Idea 2 study for GATE... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
+1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 ankuj2...@gmail.comwrote: 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
@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 rahul23111...@gmail.com wrote: +1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 ankuj2...@gmail.comwrote: 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
@Bittu...When we choose low as 2^(n-1) and high as 2^n we are reducing the complexity from O(n) (Linear Search ) to logn (base2) . Here the thing is to apply normal binary search between low and high and thats where we decrease the complexity . If the required element is not in this range we change low=high and high = 2*high and again apply Binary Search. In the code before applying binary search u each time check whether k a[high] . If not we change low and high else apply binary search here . Ideally the complexity would be lot less than log(n) but since the no is infinite and k can also be taken very very high then say k lies between 2*(10^9) and 4*(10^9) which is a very high number in Itself . n is that very high number This approach wont work if the infinite array is not sorted Regards Ankur On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com 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 rahul23111...@gmail.com wrote: +1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com 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 sunny816.i...@gmail.com 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 ankuj2...@gmail.comwrote: 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
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 bittu...@gmail.com 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 rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com 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 sunny816.i...@gmail.com
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 ankuj2...@gmail.comwrote:
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
suppose the element doesn't lies in the array and is bigger than the biggest
number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel ravindra.it...@gmail.comwrote:
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 bittu...@gmail.com 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 rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
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
sunny816.i...@gmail.com 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 ankuj2...@gmail.comwrote:
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
@Ankur I know that the complexity reduces from linear time (constant length
range checks) to logarithmic time (exponential length range checks). I was
just explaining the reason for not choosing any other number like say 3 to
compute the exponential ranges [3^(k-1)...3^k] in which case the complexity
still remains logarithmic.
On 24 October 2011 21:43, ravindra patel ravindra.it...@gmail.com wrote:
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 bittu...@gmail.com 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 rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
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
sunny816.i...@gmail.com 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 ankuj2...@gmail.comwrote:
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Search an element in an Infinite array
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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
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 ankuj2...@gmail.com 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
Do a binary Search between a[2**(k-1)] and a[2**(k)] just find kth element greater than the item to be searched. On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: 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 ankuj2...@gmail.com 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
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 sunny816.i...@gmail.comwrote: 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 ankuj2...@gmail.com 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
