1
class Solution {
2
  public int search(int[] nums, int target) {
3
    int pivot = findPivot(nums);
4
    int ans = binarySearch(nums, target, 0, pivot);
5
    if (ans != -1) {
6
      return ans;
7
    }
8
    return binarySearch(nums, target, pivot + 1, nums.length - 1);
9
  }
10

11
  public int findPivot(int[] arr) {
12
    int start = 0, end = arr.length - 1;
13
    while (start <= end) {
14
      int mid = start + (end - start) / 2;
15
      if (mid < end && arr[mid] > arr[mid + 1]) {
16
        return mid;
17
      }
18
      if (mid > start && arr[mid - 1] > arr[mid]) {
19
        return mid - 1;
20
      }
21
      if (arr[mid] <= arr[start]) {
22
        end = mid - 1;
23
      } else {
24
        start = mid + 1;
25
      }
26
    }
27
    return -1;
28
  }
29

30
  public int binarySearch(int[] arr, int target, int start, int end) {
31

32
    while (start <= end) {
33
      int mid = start + (end - start) / 2;
34

35
      if (target < arr[mid]) {
36
        end = mid - 1;
37
      } else if (target > arr[mid]) {
38
        start = mid + 1;
39
      } else {
40
        return mid;
41
      }
42
    }
43
    return -1;
44
  }
45
}