@dave:how can we find value of 'k' in (log n)
On Thu, Aug 4, 2011 at 5:41 PM, kartik sachan wrote:
> @amit it's given that array is increasing then decreasing..so where
> there is change from incre to drece that value of i in loop will be k
>
> in this we can find out k if not given
>
> -
@amit it's given that array is increasing then decreasing..so where
there is change from incre to drece that value of i in loop will be k
in this we can find out k if not given
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post
Problem 2 can be solved in O(n/k).
If you want to search for x, look at the first element. If the element
is not found, find the difference between the current element and x,
let this be stored in diff. Now, x will be atleast diff number of
positions ahead in the array. So, the next position is cu
if k is known to us the searching can be done in log(n) time
if k is not known to us ,we first find the k then solution in O(n) time
correct me if i am worng...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send ema
if we do not know k, how do we find it?
inthe series : 17 15 13 11 9 1 3 5 7
we can take k at element 1 also as the descending series can be 17 15 13 11
9 1 and ascending 3 5 7
OR
descending 17 15 13 11 9 and ascending 1 3 5 7
isn't there any relationship in kth and (k+1)th element that helps us
For question two ,
try this.
see te element at arr[0] . and supose you have to find k . if arr[0]==k ,
then yes we found the element else see the diff betweem arr[0] and k. that
will be minimum amount of steps needed to convert a[0] to k(let abs(a[0]-k)
= p). then repeat the procedure again at the
@Dave ..for question 1 why use binary search for 1to k initially say array
is
17 15 13 11 9 1 3 5 7 the kth element is 9 ..Now if u want to find 3 why to
search in first half ..Just compare with kth element and if greater find on
left else go to right :)
Not totally conviced with ur solution for
Dave's solution looks gud to me :)
On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg wrote:
> Q1 can be looked as rotated sorted array...check whether the no is less or
> greater than kth element ..if greater search using binary search with low =0
> high k-1 and if less earch in right with low=k+1 high
Q1 can be looked as rotated sorted array...check whether the no is less or
greater than kth element ..if greater search using binary search with low =0
high k-1 and if less earch in right with low=k+1 high =n;
q2) Dont know :(
On Wed, Aug 3, 2011 at 3:44 PM, Dave wrote:
> @Tushar: For problem
