1
class Solution {
2
 public:
3
  int search(vector<int> &nums, int target) {
4
    int n = nums.size() - 1;
5
    if (nums[0] == target) return 0;
6
    if (nums.size() == 1) return -1;
7
    // find the index of the minimum element ie pivot
8
    int pivot = -1;
9
    int low = 0;
10
    int high = n;
11
    while (low <= high) {
12
      int mid = (low + high) / 2;
13
      if (mid == 0) {
14
        if (nums[mid] < nums[mid + 1] && nums[mid] < nums[n]) {
15
          pivot = mid;
16
          break;
17
        } else {
18
          low = mid + 1;
19
        }
20
      }
21

22
      else if (mid == n) {
23
        if (nums[mid] < nums[0] && nums[mid] < nums[mid - 1]) {
24
          pivot = mid;
25
          break;
26
        } else {
27
          high = mid - 1;
28
        }
29
      } else if (nums[mid] < nums[mid + 1] && nums[mid] < nums[mid - 1]) {
30
        pivot = mid;
31
        break;
32
      } else if (nums[mid] >= nums[0] && nums[mid] <= nums[n])
33
        high = mid - 1;
34
      else if (nums[mid] >= nums[0])
35
        low = mid + 1;
36
      else if (nums[mid] < nums[0])
37
        high = mid - 1;
38
    }
39
    cout << pivot << endl;
40
    if (target < nums[0]) {
41
      int low1 = pivot;
42
      int high1 = n;
43
      while (low1 <= high1) {
44
        int mid1 = (low1 + high1) / 2;
45
        if (nums[mid1] == target)
46
          return mid1;
47
        else if (nums[mid1] > target)
48
          high1 = mid1 - 1;
49
        else if (nums[mid1] < target)
50
          low1 = mid1 + 1;
51
      }
52
    }
53
    if (target > nums[0]) {
54
      int low2 = 0;
55
      int high2 = pivot - 1;
56
      if (pivot == 0) {
57
        low2 = 0;
58
        high2 = n;
59
      }
60
      while (low2 <= high2) {
61
        int mid2 = (low2 + high2) / 2;
62
        if (nums[mid2] == target)
63
          return mid2;
64
        else if (nums[mid2] > target)
65
          high2 = mid2 - 1;
66
        else if (nums[mid2] < target)
67
          low2 = mid2 + 1;
68
      }
69
    }
70
    return -1;
71
  }
72
};