nope it will not work....
top kya lower part bhi sorted hai......
like 7 8 9 1 2 3 4 5 6
do it with this i/p... it will fail
ur algo will do same thing for 8 and 4
FAIL !!!
On Fri, Aug 12, 2011 at 9:27 PM, KK <kunalkapadi...@gmail.com> wrote:
> 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 <sagarpar...@gmail.com> 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 <shashank7andr...@gmail.com
> >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 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.
> >
> > --
> > **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 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.
>
>
--
**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 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.
