Very sorry the mistake. I'm not familiar with your name, and few
computer science students where I live are women.
The first detail is that binary search will only work if you assume no
duplicates. This is easy to see if you envision an input that is all
1's except for a single 2. In order to discover k, you must locate
the 2, but there is no way for a binary search to decide which half of
an array the 2 is in by looking only at the boundaries of the halves.
So begin by assuming that there are no repeats. And let's also assume
the array before rotation was in ascending order.
One way to think about the search is to look for k0 and k such that k
= k0 + 1 and A[k0] > A[k]. These are just two adjacent elements that
are out of order. So k is the number of places A is rotated to the
right. Example: A = [42, 1000, 1001, 2, 5, 7, 8]. Here k0 is 2 and
k is 3.
We can get a binary search by inventing a variable k1 and establishing
the loop invariants k0 < k1, A[k0] > A[k1]. We must move k0 closer to
k1 in each iteration by a fraction of the remaining difference. When
k1 = k0 + 1, we are done.
We can establish the invariants initially with k0=0 and k1=N-1. If
the array is rotated, then it must be true that A[0] > A[n-1].
Otherwise the array is not rotated at all (i.e. k=0).
The last important detail is that you need to take care that the
search always makes progress. If you're not careful that at least one
element is eliminated in each iteration, the search enters an endless
loop.
To prevent this problem note that if you compute the location of the
middle element with
m = (k0 + k1) / 2
then since you know k1 > k0 + 1 (otherwise the search is over), you
can be sure k1 >= k0 + 2 and, consequently,
m >= (k0 + k0 + 2) / 2
= k0 + 1.
This tells us to use the two slices A[k0..m-1] and A[m..N-1] in our
search. Both of these must have at least 1 element. This makes for 3
possibilities. If A[k0] > A[m-1], we want to keep this section of the
array and ignore the other half, so set k1=m-1. If A[m] > A[k1], we
keep this section and ignore the other half, so set k0=m. Finally, we
could have A[m-1] > A[m], which means we've been lucky: k=m and we're
done.
Coding this up in C:
#include <stdio.h>
// Special binary search to determine number of positions
// that A is rotated to the right after being sorted ascending.
int get_right_rotation(int *A, int n)
{
int k0 = 0;
int k1 = n - 1;
if (n < 2 || A[k0] < A[k1])
return 0;
while (k1 > k0 + 1) {
int m = (k0 + k1) / 2;
if (A[k0] > A[m - 1])
k1 = m - 1;
else if (A[m] > A[k1])
k0 = m;
else
return m;
}
return k1;
}
// Search
int search_rotated(int *A, int n, int val)
{
int k = get_right_rotation(A, n);
int lo = 0;
int hi = n - 1;
while (lo <= hi) {
int m = (lo + hi) / 2;
int i = (m + k) % n;
if (A[i] < val)
lo = m + 1;
else if (A[i] > val)
hi = m - 1;
else
return i;
}
return -1; // fail
}
int main(void)
{
#define N 6
int a[] = { 2, 5, 9, 42, 99, 131, 167, 234, 319, 912 };
int A[N], i, k;
// try all possible rotations
for (k = 0; k < N; k++) {
// Fill in the rotated version of the array.
for (i = 0; i < N; i++)
A[(i + k) % N] = a[i];
// Try to find all elements.
for (i = 0; i < N; i++) {
int x = search_rotated(A, N, a[i]);
if (x < 0) {
fprintf(stderr, "Failed on k=%d, val=%d\n", k, a[i]);
return 1;
}
}
}
fprintf(stderr, "success\n");
return 0;
}
On Aug 8, 10:29 am, ashita dadlani <ash....@gmail.com> wrote:
> first of all Gene..this is not "he" but "she" :P
> and secondly,can you please mention the details you are talking about so
> that we can reach to a solution?
>
>
>
> On Sun, Aug 8, 2010 at 7:48 PM, Gene <gene.ress...@gmail.com> wrote:
> > Well, then, you must say that in the problem! To to find k, ashita
> > dadlani's solution works fine, except he has left out important
> > details. This binary search is a bit tricker that the one to find a
> > value.
>
> > On Aug 8, 2:34 am, Manjunath Manohar <manjunath.n...@gmail.com> wrote:
> > > hey wait a sec,.. we wont be given the k value..
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
