int findPivot(int arr[], int low, int high)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if(arr[mid] > arr[mid + 1])
return mid;
if(arr[low] > arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}
int pivotedBinarySearch(int arr[], int arr_size, int no)
{
int pivot = findPivot(arr, 0, arr_size-1);
printf("\n%d\n",pivot);
if(arr[pivot] == no)
return pivot;
if(arr[0] <= no)
return binarySearch(arr, 0, pivot-1, no);
else
return binarySearch(arr, pivot+1, arr_size-1, no);
}
On Sat, Jul 3, 2010 at 12:47 PM, Abhirup Ghosh <[email protected]> wrote:
> How can you find smallest element in the array in O(logn) time? Can
> you please elaborate?
>
> -Abhirup
>
>
>
> On Fri, Jul 2, 2010 at 3:44 PM, jalaj jaiswal <[email protected]>
> wrote:
> > second question can be done in O(logn)
> > do a modified binary search to find the starting index of the rotated
> array
> > i.e the smallest element.
> >
> > after that you have two sorted arrays..
> > for eg 789 1236 (your modified binary search should return index of 1)
> > now check if the elemnent you are searching in greater then a[min] then
> do
> > binary search in 1st array
> > else do in second array
> >
> >
> >
> >
> > On Fri, Jul 2, 2010 at 3:29 PM, Abhirup Ghosh <[email protected]>
> wrote:
> >>
> >> 1. (1) Maintain a hash table and insert the elements in the table when
> >> passing through the array. And if there is a collision then that
> >> element is a duplicate element in the array.Time - O(n) and the space
> >> is O(n).
> >> (2) Duplicate is detected by the above process. Then it can be easily
> >> removed. I can't get what it means that remove duplicates without
> >> hampering the array! The hash table anyway would contain all the
> >> distinct elements.
> >>
> >> 2. Pass the array checking if the current element is lower than the
> >> previous one. If found such element The current element is the start
> >> of the original sorted array. If such element is not found then the
> >> first element of the present is the desired element. Note down the
> >> index. Takes O(n).
> >>
> >> Now do binary search. The mid point of the array is manipulated by
> >> considering the index that we have saved. One trivial method could be
> >> keep track of the array in each recursion and then get the half length
> >> and then calculate the index according to the placement of the
> >> starting index at that recursion. This takes O(logn).
> >>
> >> So overall Time O(n). Space O(1) [no extra space].
> >>
> >>
> >> Correct me if I am wrong.
> >>
> >> -Abhirup
> >>
> >>
> >>
> >>
> >> On Fri, Jul 2, 2010 at 1:50 AM, Vikas Jayaprakash
> >> <[email protected]> wrote:
> >> > Hi AlgoGeeks,
> >> > Can anyone provide me answers for the below.
> >> >
> >> > 1. given an array of random integers write a program to (1) detect
> >> > duplicate (2) remove duplicate (array should not get hampered at any
> >> > cost!).
> >> > 2 - In a sorted array some of the elements say N are rotated. for
> >> > example initially 1 2 3 6 7 8 9 after rotation of 3 elements 7 8 9 1 2
> >> > 3 6.So how do you search an element in this array?
> >> >
> >> >
> >> > Regards,
> >> > Vikas J
> >> >
> >> > --
> >> > 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]<algogeeks%[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]<algogeeks%[email protected]>
> .
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> >
> >
> > --
> > With Regards,
> > Jalaj Jaiswal
> > +919026283397
> > B.TECH IT
> > 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%[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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 [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.
