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 <nikutel...@gmail.com> 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 <akanksha.271...@gmail.com>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 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.