Binary search is sufficient for this particular case. To help the explain, we assume the circular sorted array is ascending if probably rotated. we use *d[0..n - 1]* to represent the array with n elements and *v* to represent the searched number.
Observing the circular sorted sequence d[0..n - 1]: 6 ,7 ,8 ,1 ,2 ,3 ,4 ,5 we can find that: 1) d[0] >= d[n - 1] 2) there exists one x that d[0..x] is ascending and d[x + 1.. n - 1] is also ascending Using the rules above, we can simply get an binary search algorithm: The C++ code is below: http://fayaa.com/code/view/20170/ *C++语言*: Codee#20170 <http://fayaa.com/code/view/20170/> #include <cstdio> using namespace std; // Parameters: // @d: is one circularly sorted array, it looks like 6, 7, 8, 1, 2, 3, 5, 6 // @v: is the searched number // Returns: -1 if not found or return the index int BinarySearch(int d[], int len, int v) { if(d == NULL || len <= 0) return -1; int left = 0, right = len - 1; while(right - left > 1) { int mid = (left + right) >> 1; if(d[mid] >= d[left]) { if(v >= d[mid]) left = mid; else if(v >= d[left]) right = mid; else left = mid; } else // d[mid] < d[left] { if(v < d[mid]) right = mid; else if(v < d[left]) left = mid; else right = mid; } } if(d[left] != v) return -1; return left; } int main() { int d[] = {6, 7, 8, 1, 2, 3, 4, 5}; for(int i = 0; i < 10; i++) { printf("%d: %d\n", i, BinarySearch(d, 8, i)); } return 0; } 2011/6/11 L <prnk.bhatna...@gmail.com> > Use ternary search to find the minimum number. (In this case 1) > Then you have two sorted arrays, one ascending and one descending. > Now, you can apply binary search. First, check the number with the > last element and the first element and chose the appropriate array for > searching. > > Time complexity: O(log n) > Space complexity: O(1). > > On Jun 10, 9:06 pm, coder dumca <coder.du...@gmail.com> wrote: > > hi frndz > > > > given an array which is circularly sorted like > > > > 6 ,7 ,8 ,1 ,2 ,3 ,4 ,5 > > search a given number. > > -- > 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. > > -- 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.
