Check this out....
//But this and fails for input such as: 11111011111.... ie all nos
must be unique..
int search_element_in_rotated_array(int *a, int low, int high, int
key)
{
while(low <= high)
{
int mid = low + (high - low)/2;
if(a[mid] == key)
return mid;
if(a[mid] >= a[low]) // the top part is sorted
{
if(a[low] <= key && key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
else
{
if(key <= a[high] && key > a[mid])
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
On Aug 12, 8:38 pm, sagar pareek <[email protected]> wrote:
> oh common shashank...its not that easy u told.....
> just do coding....then u will find the error in ur logic
>
> On Fri, Aug 12, 2011 at 6:25 PM, WgpShashank
> <[email protected]>wrote:
>
>
>
>
>
>
>
>
>
> > Hi Guys Here is the algorithm for doing same in O(logn)
>
> > Hint : Find the pivot point, divide the array in two sub-arrays and call
> > binary search. Thats It :)
>
> > Algorithm
> > 1. A Pivot Point is point around which array is rotated so 1st we need to
> > find out its location/index. lets say it pivot.
> > a. to find pivot point we use same idea of binary search & check if
> > arr[mid]>a[mid+1] if true then return pivot=mid.
> > b else if arr[low]<a[mid] search for pivot in left
> > c. else search for pivot in right half of array.
> > Time Complexity O(logn)
>
> > 2. Once we have found index of pivot point check if desired element is
> > same value at pivot index or not e.g.
> > a. ( if a[pivot]==value we are searching for ) the simply return true
> > or 1 .
> > Now call binary search for one of the two sub-arrays.
> > (ab) *If *element is greater than 0th element then search in
> > left array
> > (ac) *Else* Search in right array *
> > (ad) If *element is found in selected sub-array then return
> > index
> > *Else *return -1.
>
> > Again Time Complexity O(logn)
>
> > Hope You Can Make it in Running Code , Do Noify me if You Need More
> > Explanation or if missed Something??
>
> > *Regards
> > Shashank Mani "Computer Science Is Awesome So Why I Write Code"
> > Computer Science
> > Birla institute of Technology Mesra
> > *
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To view this discussion on the web visit
> >https://groups.google.com/d/msg/algogeeks/-/QPCzNLNf_sEJ.
>
> > 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.
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT 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.
