Modified Piyush's soln to handle the above case.
int get_pivot(int a [ ],int low, int high)
{
if (low < high)
{
int mid = (low+high)/2;
if(a[mid]>a[mid+1])
return mid+1;
if(a[low]>a[mid])
return (get_pivot(a,low,mid-1));
else
return(get_pivot(a,mid+1,high);
}
return -1; // ie no pivot exists. so rotation must be 0
);
int getMin(int a[], int n) {
int min = get_pivot(a,0,n);
if (min > 0) return a[min];
else return a[0]
}
Thanks,
Immanuel
On Sat, May 28, 2011 at 11:01 PM, Dumanshu <[email protected]> wrote:
> It won't work if we rotate the array by 0. So is that the xtra case do
> we have to consider???
>
> On May 28, 7:18 pm, Piyush Sinha <[email protected]> wrote:
> > The main idea is to get the point at which the the rotation is
> > made...It can be done in O(lgN) time complexity...
> >
> > int get_pivot(int a [ ],int low, int high)
> > {
> > int mid = (low+high)/2;
> > if(a[mid]>a[mid+1])
> > return (a[mid+1]);
> > if(a[low]>a[mid])
> > return (get_pivot(a,low,mid-1));
> > else
> > return(get_pivot(a,mid+1,high));
> >
> > }
> >
> > On 5/28/11, Dumanshu <[email protected]> wrote:
> >
> > > Find an elegant way of getting the minimum value in a sorted array but
> > > it has been rotated by some number.
> > > say u had the array as 4 , 5, 6, 7, 8,9 and u rotate it by 2. u get
> > > 6,7,8,9,4,5. Now u have to find minimum number in this modified array.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > *Piyush Sinha*
> > *IIIT, Allahabad*
> > *+91-8792136657*
> > *+91-7483122727*
> > *https://www.facebook.com/profile.php?id=100000655377926*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
