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 an14      * 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 ordered31             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 ordered38             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 repeats46             if (list[mid] != list[right]) {47                 return search(list, mid + 1, right, x);48             } else {49                 // search both halves50                 int result = search(list, left, mid - 1, x);51                 if (result == -1)52                     return search(list, mid + 1, right, x);53                 else54                     return result;55             }56         }57     }58 }