@Amit: It is given that the array is decreasing, then increasing. An
array of constants is neither increasing nor decreasing.
Dave
On Aug 3, 11:41 pm, amit karmakar amit.codenam...@gmail.com wrote:
Can you show how to find k for an array containing n 2's using binary
search.
On Aug 4, 6:29
@Kartik: k can be found with a binary search. Once k is known, the key
can be found with one or two binary searches. O(log n).
Dave
On Aug 3, 11:08 pm, kartik sachan kartik.sac...@gmail.com wrote:
if k is known to us the searching can be done in log(n) time
if k is not known to us ,we first
@Tushar: Either value of k will work. You are going to search both
sides of k.
Dave
On Aug 3, 10:59 pm, Tushar Bindal tushicom...@gmail.com wrote:
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
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
@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
@dave:how can we find value of 'k' in (log n)
On Thu, Aug 4, 2011 at 5:41 PM, kartik sachan kartik.sac...@gmail.comwrote:
@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
@Kamakshii: Do a binary search on a[i] - a[i-1]. If this is negative,
i is in the decreasing range, i.e., i k, so reset the lower limit of
the interval. If it is positive, i is in the increasing range, i.e., i
k, so reset the upper limit of the interval. Quit when the interval
length is 1. Let k
@Tushar: For problem 1, do a binary search on elements 1 to k, and if
no hit is found, do a binary search on elements k+1 to n.
For problem 2, suppose that you are searching the given array for the
number 2. The idea is to take big steps when you are far from the
target, and small steps when you
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 dave_and_da...@juno.com wrote:
Dave's solution looks gud to me :)
On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com 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
@Ankur: Not a rotated sorted array. The given array looks like a V,
but the rotated sorted array would look like
/
/
Dave
On Aug 3, 2:52 pm, Ankur Garg ankurga...@gmail.com wrote:
Q1 can be looked as rotated sorted array...check whether the no is less or
greater than kth element ..if greater
I think for question 1, the value of k is not provided, right?
On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote:
Dave's solution looks gud to me :)
On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote:
Q1 can be looked as rotated sorted array...check whether 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
But what if the kth element is the 1? That's permitted by the problem
statement. And my solution is O(log n), which is of optimal order.
Dave
On Aug 3, 3:23 pm, Ankur Garg ankurga...@gmail.com wrote:
@Dave ..for question 1 why use binary search for 1to k initially say array
is
17 15 13 11 9
@Amit: If k is not known, you can find it with another binary search.
Dave
On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote:
I think for question 1, the value of k is not provided, right?
On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote:
Dave's solution looks gud
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
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
Can you show how to find k for an array containing n 2's using binary
search.
On Aug 4, 6:29 am, Dave dave_and_da...@juno.com wrote:
@Amit: If k is not known, you can find it with another binary search.
Dave
On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote:
I think for
18 matches
Mail list logo
