CC150 - 11.3

 1 package POJ;
 2 
 3 import java.util.Arrays;
 4 import java.util.Comparator;
 5 import java.util.Hashtable;
 6 import java.util.LinkedList;
 7 import java.util.List;
 8 
 9 public class Main {
10 
11     /**
12      * 
13      * 11.3 Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an
14      * element in the array. You may assume that the array was originally sorted in increasing order.
15      * 
16      */
17     public static void main(String[] args) {
18         Main so = new Main();
19         int[] list = { 10, 15, 20, 0, 5 };
20         System.out.println(so.search(list, 0, 4, 5));
21     }
22 
23     public int search(int[] list, int left, int right, int x) {
24         int mid = (right + left) / 2;
25         if (x == list[mid])
26             return mid;
27         if (left > right)
28             return -1;
29         if (list[left] < list[mid]) {
30             // left is normally ordered
31             if (x >= list[left] && x <= list[mid]) {
32                 return search(list, left, mid - 1, x);
33             } else {
34                 return search(list, mid + 1, right, x);
35             }
36         } else if (list[left] > list[mid]) {
37             // right is normally ordered
38             if (x >= list[mid] && x <= list[right]) {
39                 return search(list, mid + 1, right, x);
40             } else {
41                 return search(list, left, mid - 1, x);
42             }
43         } else {
44             // list[left]==list[mid]
45             // left half is all repeats
46             if (list[mid] != list[right]) {
47                 return search(list, mid + 1, right, x);
48             } else {
49                 // search both halves
50                 int result = search(list, left, mid - 1, x);
51                 if (result == -1)
52                     return search(list, mid + 1, right, x);
53                 else
54                     return result;
55             }
56         }
57     }
58 }