@jalaj: u are more or less right....actually u check first that
whether the given seq first increases or dec then accordingly call
function....here u have assumed that seq first increases n then
decreases so first u better check either increases or decreases.....bt
overall good buddy......!!!
On 2/14/11, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote:
> 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.
>
>
--
Sent from my mobile device
--
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.
