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 <[email protected]> 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 <[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.
>
--
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.
