5 7 9 17 21 20 19 18
monotonic sequence consists of one increasing and 1 decreasing sequence
so first lets find out pivot position .. can be done with modified binary
search to find out two array
first then applying binary search on both the arrays.. total O(logn) +
O(logn1) +O(logn2) n>n1,n2
int modi_binary(int *a,int i, int j){
if(i<j){
int mid=(i+j)/2;
if((a[mid]>a[mid+1])&&(a[mid-1]<a[mid])) return mid;
else if(a[mid]>a[mid-1])&&(a[mid]<a[mid+1]) return modi_binary(int
*a,int mid+1, int j);
else if(a[mid]<a[mid-1])&&(a[mid]>a[mid+1]) return modi_binary(int
*a,int i, int mid-1);
}
if(i==j) return i;
}
int search(int *a,int low,int high, int key){
int pivot=modi_binary(a,low,high);
int k1=binaryserach(a,low,k-1,key);
int k2=binarysearch(a,k,high,key); //normal binary search
return k1?k1:k2 //i'm assuming only 1 occurence of key
}
correct me if i am wrong !!!!
On Mon, Feb 14, 2011 at 9:40 PM, MONSIEUR <monsieur....@gmail.com> wrote:
> how will you search an element in a bitonic sequence.... Time
> complexity should be lessthan linear time
>
> --
> 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.
>
>
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
B.Tech 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 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.
