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 <[email protected]> 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<iostream> > #include<cmath> > #include<stdlib.h> > 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<<a[i]<<" "; > int mid=(int)(l+r)/2; > > if(a[mid]==ele) > { cout<<"\n\nFound the element at index"<<mid<<endl; > return ;} > if(a[l]==ele) > { cout<<"\n\nFound the element at index"<<l<<endl; > return ;} > if(a[r]==ele) > { cout<<"\n\nFound the element at index"<<r<<endl; > return ;} > > if(a[l]<a[mid]) > { > if(ele>a[l] && ele<a[mid]) > search(a,l+1,mid-1,ele); > } > else > { > if(ele>a[l] || ele<a[mid]) > search(a,l+1,mid-1,ele); > } > > > if(a[r]>a[mid]) > { > if(ele<a[r] && ele>a[mid]) > search(a,mid+1,r-1,ele); > } > else > { > if(ele<a[r] || ele>a[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 [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.
