Re: [algogeeks] Re: Modified binary search
+1 Gene With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Wed, Sep 28, 2011 at 1:36 AM, Gene wrote: > Indeed you must be given that all the array elements are unique or at > least that there are no more than floor(n/2) repeats). Otherwise this > is impossible. The simplest way to think about it is first to search > for i such that a[i] > a[i+1]. At that point you know there are two > sorted ranges a[0]..a[i] and a[i+1] to a[n-1], so you can use regular > binary search on each of these pieces. > > So how to find i? This is itself a binary search. At each stage, > check whether a[0] > a[mid] and a[mid] > a[n-1]. The half that passes > this test contains i. So throw away the other. > > On Sep 27, 10:01 am, Decipher wrote: > > A given sorted array is rotated unknown number of times , write a C/C++ > code > > to find an element in the sorted array in O(log n) time . > > > > I know the solution to this problem is through binary search , but don't > > know the exact solution . Please help !! > > -- > 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.
[algogeeks] Re: Modified binary search
Indeed you must be given that all the array elements are unique or at least that there are no more than floor(n/2) repeats). Otherwise this is impossible. The simplest way to think about it is first to search for i such that a[i] > a[i+1]. At that point you know there are two sorted ranges a[0]..a[i] and a[i+1] to a[n-1], so you can use regular binary search on each of these pieces. So how to find i? This is itself a binary search. At each stage, check whether a[0] > a[mid] and a[mid] > a[n-1]. The half that passes this test contains i. So throw away the other. On Sep 27, 10:01 am, Decipher wrote: > A given sorted array is rotated unknown number of times , write a C/C++ code > to find an element in the sorted array in O(log n) time . > > I know the solution to this problem is through binary search , but don't > know the exact solution . Please help !! -- 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] Re: Modified binary search
first find the place where the mismatch occours in the array linearly ..
like if the the array is in increasing sorted order than first find a
location where it violates this property
{8,9,18,19,22,25,36,2,3,5,6,7};
the property is violated at index 7
now u have 2 sorted arrays from index [0-6] and [7-11]
now use binary search on both of these arrays as both are sorted, and get
the answer.
On Wed, Sep 28, 2011 at 12:11 AM, raju wrote:
> Rotated array => [ 0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0 ]
> find 1 using binary search ...
>
> turns out we cant use binary search if we've repeated elements in rotated
> array ...
>
> ~raju
>
>
> On Tue, Sep 27, 2011 at 8:18 PM, akanksha wrote:
>
>> /*
>> A program in which an array have an increasing sequence and an
>> decreasing sequence .
>> in these array search an element in o(n)time complexity
>> these is also called rotated array
>> */
>> #include
>> #include
>> #include
>> using namespace std;
>> void search(int *array,int intial_index,int last_index,int ele);
>> int main()
>> {
>>int array[]={8,9,18,19,22,25,36,2,3,5,6,7};
>>
>>search(array,0,11,9);
>>
>>return 0;
>> }
>> void search(int *a,int l,int r,int ele) //l:left and r:right
>> {
>>cout<<"\nSearch in array :";
>>for(int i=l;i<=r;i++)
>>cout<>int mid=(int)(l+r)/2;
>>
>>if(a[mid]==ele)
>> { cout<<"\n\nFound the element at index"<>return ;}
>>if(a[l]==ele)
>> { cout<<"\n\nFound the element at index"<>return ;}
>>if(a[r]==ele)
>> { cout<<"\n\nFound the element at index"<>return ;}
>>
>>if(a[l]>{
>>if(ele>a[l] && ele>search(a,l+1,mid-1,ele);
>>}
>>else
>>{
>>if(ele>a[l] || ele>search(a,l+1,mid-1,ele);
>>}
>>
>>
>>if(a[r]>a[mid])
>>{
>>if(elea[mid])
>>search(a,mid+1,r-1,ele);
>>}
>>else
>>{
>>if(elea[mid])
>>search(a,mid+1,r-1,ele);
>> }
>>
>>
>>
>>
>> }
>>
>> --
>> 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] Re: Modified binary search
Rotated array => [ 0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0 ]
find 1 using binary search ...
turns out we cant use binary search if we've repeated elements in rotated
array ...
~raju
On Tue, Sep 27, 2011 at 8:18 PM, akanksha wrote:
> /*
> A program in which an array have an increasing sequence and an
> decreasing sequence .
> in these array search an element in o(n)time complexity
> these is also called rotated array
> */
> #include
> #include
> #include
> using namespace std;
> void search(int *array,int intial_index,int last_index,int ele);
> int main()
> {
>int array[]={8,9,18,19,22,25,36,2,3,5,6,7};
>
>search(array,0,11,9);
>
>return 0;
> }
> void search(int *a,int l,int r,int ele) //l:left and r:right
> {
>cout<<"\nSearch in array :";
>for(int i=l;i<=r;i++)
>cout
>if(a[mid]==ele)
> { cout<<"\n\nFound the element at index"if(a[l]==ele)
> { cout<<"\n\nFound the element at index"if(a[r]==ele)
> { cout<<"\n\nFound the element at index"
>if(a[l]{
>if(ele>a[l] && elesearch(a,l+1,mid-1,ele);
>}
>else
>{
>if(ele>a[l] || elesearch(a,l+1,mid-1,ele);
>}
>
>
>if(a[r]>a[mid])
>{
>if(elea[mid])
>search(a,mid+1,r-1,ele);
>}
>else
>{
>if(elea[mid])
>search(a,mid+1,r-1,ele);
> }
>
>
>
>
> }
>
> --
> 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.
[algogeeks] Re: Modified binary search
/*
A program in which an array have an increasing sequence and an
decreasing sequence .
in these array search an element in o(n)time complexity
these is also called rotated array
*/
#include
#include
#include
using namespace std;
void search(int *array,int intial_index,int last_index,int ele);
int main()
{
int array[]={8,9,18,19,22,25,36,2,3,5,6,7};
search(array,0,11,9);
return 0;
}
void search(int *a,int l,int r,int ele) //l:left and r:right
{
cout<<"\nSearch in array :";
for(int i=l;i<=r;i++)
cout
[algogeeks] Re: Modified Binary Search
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
// 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 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 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 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 > .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.
Re: [algogeeks] Re: Modified Binary Search
check out this link guys,,, for more implementation details On Sun, Aug 8, 2010 at 7:59 PM, ashita dadlani 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 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 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 >> . >> 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. > -- With Regards, *Jalaj Jaiswal* (+919026283397) Final Year Undergraduate, IIIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Modified Binary Search
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 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 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 > . > 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.
[algogeeks] Re: Modified Binary Search
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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Modified Binary Search
its possible.first apply binary search to find the index where the array is rotated. eg.a=[8,9,1,2,3,4,56,7] first apply binary search to find the value i=2. now we have 2 sub sorted arrays,ie, from i=0 to i=1 and from i=2 to i=8. apply binary search to these sub sorted arrays each of which will take time logn. hence total time:O(3logn)=O(logn) On Sun, Aug 8, 2010 at 12:04 PM, Manjunath Manohar 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 > . > 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.
Re: [algogeeks] Re: Modified Binary Search
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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Modified Binary Search
On Aug 7, 4:41 pm, AlgoBoy wrote: > is there a way to apply a binary search on a sorted array...with a > catch... the array is rotated k times clockwise > > Example...4,5,1,2,3... > > I heard a binary search is possible.. Of course it's possible. If the array A has N items, then just replace every reference in the normal binary search A[I] with A[(I+k) mod N] (or (I-k) mod N depending on how you define "clockwise"). The algorithm will see the "unrotated" version of the array. -- 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.
