Given a circle sorted array, please write a function to search a number and output its position.
Example:
Find number 6 in array { 1,2,3,4,5,6,7 }, output is 5
Find number 6 in array { 5,6,7,1,2,3,4 }, output is 1
My Answer: (I am no sure if it is correct.)
#include "stdafx.h" #includeusing namespace std; int binarySearch(int n, int* a, int l, int r); int _tmain(int argc, _TCHAR* argv[]) { int a[7] = { 4, 5, 6, 7, 1, 2, 3 }; cout << binarySearch(6, a, 0, 6) << endl; cout << binarySearch(2, a, 0, 6) << endl; cout << binarySearch(5, a, 0, 6) << endl; cin.get(); return 0; } int binarySearch(int n, int* a, int l, int r) { int i = (l + r) / 2; if (n == a[i]) return i; if (a[l] < a[r]) { if (n > a[i]) { l += 1; } else { r = i - 1; } } else { if (n > a[i] || n < a[l]) { l += 1; } else { r = i - 1; } } return binarySearch(n, a, l, r); }
沒有留言:
張貼留言