| 2 | |
| 3 | public class Question { |
| 4 | public static int search(int a[], int left, int right, int x) { |
| 5 | int mid = (left + right) / 2; |
| 6 | if (x == a[mid]) { // Found element |
| 7 | return mid; |
| 8 | } |
| 9 | if (right < left) { |
| 10 | return -1; |
| 11 | } |
| 12 | |
| 13 | /* While there may be an inflection point due to the rotation, either the left or |
| 14 | * right half must be normally ordered. We can look at the normally ordered half |
| 15 | * to make a determination as to which half we should search. |
| 16 | */ |
| 17 | if (a[left] < a[mid]) { // Left is normally ordered. |
| 18 | if (x >= a[left] && x <= a[mid]) { |
| 19 | return search(a, left, mid - 1, x); |
| 20 | } else { |
| 21 | return search(a, mid + 1, right, x); |
| 22 | } |
| 23 | } else if (a[mid] < a[left]) { // Right is normally ordered. |
| 24 | if (x >= a[mid] && x <= a[right]) { |
| 25 | return search(a, mid + 1, right, x); |
| 26 | } else { |
| 27 | return search(a, left, mid - 1, x); |
| 28 | } |
| 29 | } else if (a[left] == a[mid]) { // Left is either all repeats OR loops around (with the right half being all dups) |
| 30 | if (a[mid] != a[right]) { // If right half is different, search there |
| 31 | return search(a, mid + 1, right, x); |
| 32 | } else { // Else, we have to search both halves |
| 33 | int result = search(a, left, mid - 1, x); |
| 34 | if (result == -1) { |
| 35 | return search(a, mid + 1, right, x); |
| 36 | } else { |
| 37 | return result; |
| 38 | } |
| 39 | } |
| 40 | } |
| 41 | return -1; |
| 42 | } |
| 43 | |
| 44 | public static void main(String[] args) { |
| 45 | int[] a = { 2, 3, 2, 2, 2, 2, 2, 2 , 2 , 2 }; |