If the array is not circular, we can use binary search to find the key. But if the array is circular we don't know where is the starting point (pivot element). Obviously we can do a linear search to find the element. But if the input array is very large the worst case performance will be very bad. We can take advantage of the fact that the array is sort and use binary search algorithm to find the element in O(N log N).

#### Approach:

`a[0] < a[mid]`

, then all values in the first half of the array are sorted. `a[mid] < a[last]`

, then all values in the second half of the array are sorted. - If so, binary search that half.
- If it doesn't, it must be in the unsorted half. Take that half and repeat this process

#include <iostream> #include <vector> #include <assert.h> template<typename T, typename type> int binary_search(const T& a, int left, int right, type key) { while (left <= right) { int mid = (right-left)/2 + left; // base case 1 if (a[mid] == key) return mid; // mid less than key. Move to right if (a[mid] < key) { left = mid+1; } else { right = mid-1; } } return -1; } template<typename T, typename type> int circular_search(const T& a, int left, int right, type key) { // base case 1 int mid = (right-left)/2 + left; if (a[mid] == key) return mid; // left array is sorted. if (a[0] < a[mid]) { if (key > a[left] && key < a[mid]) { return binary_search(a, left, mid-1, key); } else { return circular_search(a, mid+1, right, key); } } // right array is sorted else if (a[mid] < a[right]) { if (key > a[mid] && key < a[right]) return binary_search(a, mid+1, right, key); else return circular_search(a, left, mid-1, key); } return -1; } template<typename T> void print(const T&a) { typedef typename T::const_iterator iterator; iterator start = a.begin(); iterator end = a.end(); for(; start!=end; ++start) std::cout << *start << " "; std::cout << std::endl; } int main() { typedef std::vector<int> Input; Input temp; int n =0; // get n from user std::cin >> n; for(int i=0; i<n; ++i) { temp.push_back(i*2); } Input data; data.resize(temp.size()); // Rotate the input sequence std::rotate_copy(temp.begin(), temp.begin()+4, data1.end(), data.begin()); print(data); // get key from user int key=0; std::cin >> key; int found = circular_search<Input, int>(data, 0, n-1, key); if (found) { assert(key == data[found]); std::cout << data[found] << " found @ pos " << found << std::endl; } else std::cout << key << " not found" << std::endl; return 0; }

## No comments:

## Post a Comment