Re: [algogeeks] Search an array of unknown length

2011-08-19 Thread Sanjay Rajpal
You can do it very easily.

I assume array is sorted and contains integers.

Say start at position 1, if value at that index is equal to the value to be
found, return index.
else if value at that index is greater than the value to be found, we got an
interval to search in.
else(value at that index is smaller than the value to be found)
search at location 10,then 100, then 1000 till you find an interval.

Once you find an interval, perform Binary Search on this and get element in
O(log n).

Got it ?

Sanju
:)



On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek sagarpar...@gmail.comwrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an element
 in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


-- 
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 array of unknown length

2011-08-19 Thread Sanjay Rajpal
I forgot to mention one thing, at each comparison, store the index at which
we searched previously.

Sanju
:)



On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.com wrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the value to be
 found, return index.
 else if value at that index is greater than the value to be found, we got
 an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an interval.

 Once you find an interval, perform Binary Search on this and get element in
 O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek sagarpar...@gmail.comwrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an element
 in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.




-- 
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 array of unknown length

2011-08-19 Thread sagar pareek
@Sanjay
yeah its the very basic idea that comes in mind
but is your index searching log n ?
i think no !!
if yes then tell me how?

On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal srn...@gmail.com wrote:

 I forgot to mention one thing, at each comparison, store the index at which
 we searched previously.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.com wrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the value to
 be found, return index.
 else if value at that index is greater than the value to be found, we got
 an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an interval.

 Once you find an interval, perform Binary Search on this and get element
 in O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek sagarpar...@gmail.comwrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an
 element in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.



  --
 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.




-- 
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT 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 array of unknown length

2011-08-19 Thread Sanjay Rajpal
See at each step you are multiplying the index to be compared by 10(say),
this increase is exponential.
Therefore the search is exponential and complexity is log n. Base depends on
the factor by which you are multiplying for the next index to be compared.

Sanju
:)



On Fri, Aug 19, 2011 at 10:57 AM, sagar pareek sagarpar...@gmail.comwrote:

 @Sanjay
 yeah its the very basic idea that comes in mind
 but is your index searching log n ?
 i think no !!
 if yes then tell me how?


 On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal srn...@gmail.com wrote:

 I forgot to mention one thing, at each comparison, store the index at
 which we searched previously.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.com wrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the value to
 be found, return index.
 else if value at that index is greater than the value to be found, we got
 an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an interval.

 Once you find an interval, perform Binary Search on this and get element
 in O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek sagarpar...@gmail.comwrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an
 element in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.



  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


-- 
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 array of unknown length

2011-08-19 Thread sagar pareek
hmmm ok
i found a solution in which index searching is done by 2^i
which is more optimal
multiplication by 10 or 2 power i ??i=0,1,2,3.

On Fri, Aug 19, 2011 at 11:30 PM, Sanjay Rajpal srn...@gmail.com wrote:

 See at each step you are multiplying the index to be compared by 10(say),
 this increase is exponential.
 Therefore the search is exponential and complexity is log n. Base depends
 on the factor by which you are multiplying for the next index to be
 compared.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:57 AM, sagar pareek sagarpar...@gmail.comwrote:

 @Sanjay
 yeah its the very basic idea that comes in mind
 but is your index searching log n ?
 i think no !!
 if yes then tell me how?


 On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal srn...@gmail.com wrote:

 I forgot to mention one thing, at each comparison, store the index at
 which we searched previously.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.comwrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the value to
 be found, return index.
 else if value at that index is greater than the value to be found, we
 got an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an interval.

 Once you find an interval, perform Binary Search on this and get element
 in O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek 
 sagarpar...@gmail.comwrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an
 element in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.



  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




-- 
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT 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 array of unknown length

2011-08-19 Thread sagar pareek
Well i think it depends...
because range of   x and 10x is more than  i and 2i
no doubt multiple of 10 will give us early index but then to find number in
b/w indexes is more than of 2^i

On Fri, Aug 19, 2011 at 11:38 PM, Sanjay Rajpal srn...@gmail.com wrote:

 Multiplication by 10 or 2^i , it depends.

 Multiplication by 10 will be faster, I think.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 11:05 AM, sagar pareek sagarpar...@gmail.comwrote:

 hmmm ok
 i found a solution in which index searching is done by 2^i
 which is more optimal
 multiplication by 10 or 2 power i ??i=0,1,2,3.

 On Fri, Aug 19, 2011 at 11:30 PM, Sanjay Rajpal srn...@gmail.com wrote:

 See at each step you are multiplying the index to be compared by 10(say),
 this increase is exponential.
 Therefore the search is exponential and complexity is log n. Base depends
 on the factor by which you are multiplying for the next index to be
 compared.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:57 AM, sagar pareek sagarpar...@gmail.comwrote:

 @Sanjay
 yeah its the very basic idea that comes in mind
 but is your index searching log n ?
 i think no !!
 if yes then tell me how?


 On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal srn...@gmail.comwrote:

 I forgot to mention one thing, at each comparison, store the index at
 which we searched previously.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.comwrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the value
 to be found, return index.
 else if value at that index is greater than the value to be found, we
 got an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an
 interval.

 Once you find an interval, perform Binary Search on this and get
 element in O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek sagarpar...@gmail.com
  wrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an
 element in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.



  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




-- 
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT 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 array of unknown length

2011-08-19 Thread Sanjay Rajpal
Thats wat I said, it depends. Searching in the interval will compensate
reaching the index earlier.
So both are almost equivalent.

Sanju
:)



On Fri, Aug 19, 2011 at 11:12 AM, sagar pareek sagarpar...@gmail.comwrote:

 Well i think it depends...
 because range of   x and 10x is more than  i and 2i
 no doubt multiple of 10 will give us early index but then to find number in
 b/w indexes is more than of 2^i


 On Fri, Aug 19, 2011 at 11:38 PM, Sanjay Rajpal srn...@gmail.com wrote:

 Multiplication by 10 or 2^i , it depends.

 Multiplication by 10 will be faster, I think.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 11:05 AM, sagar pareek sagarpar...@gmail.comwrote:

 hmmm ok
 i found a solution in which index searching is done by 2^i
 which is more optimal
 multiplication by 10 or 2 power i ??i=0,1,2,3.

 On Fri, Aug 19, 2011 at 11:30 PM, Sanjay Rajpal srn...@gmail.comwrote:

 See at each step you are multiplying the index to be compared by
 10(say), this increase is exponential.
 Therefore the search is exponential and complexity is log n. Base
 depends on the factor by which you are multiplying for the next index to be
 compared.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:57 AM, sagar pareek 
 sagarpar...@gmail.comwrote:

 @Sanjay
 yeah its the very basic idea that comes in mind
 but is your index searching log n ?
 i think no !!
 if yes then tell me how?


 On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal srn...@gmail.comwrote:

 I forgot to mention one thing, at each comparison, store the index at
 which we searched previously.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.comwrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the value
 to be found, return index.
 else if value at that index is greater than the value to be found, we
 got an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an
 interval.

 Once you find an interval, perform Binary Search on this and get
 element in O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek 
 sagarpar...@gmail.com wrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an
 element in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.



  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT ALLAHABAD

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to 

Re: [algogeeks] Search an array of unknown length

2011-08-19 Thread sagar pareek
:)

On Fri, Aug 19, 2011 at 11:43 PM, Sanjay Rajpal srn...@gmail.com wrote:

 Thats wat I said, it depends. Searching in the interval will compensate
 reaching the index earlier.
 So both are almost equivalent.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 11:12 AM, sagar pareek sagarpar...@gmail.comwrote:

 Well i think it depends...
 because range of   x and 10x is more than  i and 2i
 no doubt multiple of 10 will give us early index but then to find number
 in b/w indexes is more than of 2^i


 On Fri, Aug 19, 2011 at 11:38 PM, Sanjay Rajpal srn...@gmail.com wrote:

 Multiplication by 10 or 2^i , it depends.

 Multiplication by 10 will be faster, I think.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 11:05 AM, sagar pareek sagarpar...@gmail.comwrote:

 hmmm ok
 i found a solution in which index searching is done by 2^i
 which is more optimal
 multiplication by 10 or 2 power i ??i=0,1,2,3.

 On Fri, Aug 19, 2011 at 11:30 PM, Sanjay Rajpal srn...@gmail.comwrote:

 See at each step you are multiplying the index to be compared by
 10(say), this increase is exponential.
 Therefore the search is exponential and complexity is log n. Base
 depends on the factor by which you are multiplying for the next index to 
 be
 compared.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:57 AM, sagar pareek 
 sagarpar...@gmail.comwrote:

 @Sanjay
 yeah its the very basic idea that comes in mind
 but is your index searching log n ?
 i think no !!
 if yes then tell me how?


 On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal srn...@gmail.comwrote:

 I forgot to mention one thing, at each comparison, store the index at
 which we searched previously.

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal srn...@gmail.comwrote:

 You can do it very easily.

 I assume array is sorted and contains integers.

 Say start at position 1, if value at that index is equal to the
 value to be found, return index.
 else if value at that index is greater than the value to be found,
 we got an interval to search in.
 else(value at that index is smaller than the value to be found)
 search at location 10,then 100, then 1000 till you find an
 interval.

 Once you find an interval, perform Binary Search on this and get
 element in O(log n).

 Got it ?

 Sanju
 :)



 On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek 
 sagarpar...@gmail.com wrote:

 HI,

 I have encountered a problem :-

 You have an array of  *UNKNOWN  *length . And you have to find an
 element in  O(log(n)) time without using any extra space.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.



  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT 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.


  --
 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.




 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT ALLAHABAD

  --
 You received this message because you are subscribed to the Google