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: 101 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 codingthen 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.
