1
class Solution {
2
 public:
3
  bool search(vector<int> &nums, int target) {
4
    if (nums[0] == target or nums.back() == target) return true;
5
    // this line is redundant it reduces only the worst case when all elements
6
    // are same to O(1)
7

8
    const int n = nums.size();
9
    int l = 0, h = n - 1;
10
    while (l + 1 < n and nums[l] == nums[l + 1]) l++;
11

12
    // if all elements are same
13
    if (l == n - 1) {
14
      if (nums[0] == target)
15
        return true;
16
      else
17
        return false;
18
    }
19

20
    // while last element is equal to 1st element
21
    while (h >= 0 and nums[h] == nums[0]) h--;
22
    int start = l, end = h;
23

24
    // find the point of pivot ie from where the rotation starts
25
    int pivot = -1;
26
    while (l <= h) {
27
      int mid = l + (h - l) / 2;
28
      if (nums[mid] >= nums[0])
29
        l = mid + 1;
30
      else {
31
        pivot = mid;
32
        h = mid - 1;
33
      }
34
    }
35

36
    if (pivot == -1)
37
      l = start,
38
      h = end; // if no pivot exits then search space is from start -e end
39
    else {
40
      if (target > nums[end])
41
        l = start, h = pivot - 1; // search space second half
42
      else
43
        l = pivot, h = end; // search space first half
44
    }
45

46
    // normal binary search
47
    while (l <= h) {
48
      int mid = l + (h - l) / 2;
49
      if (nums[mid] > target)
50
        h = mid - 1;
51
      else if (nums[mid] < target)
52
        l = mid + 1;
53
      else
54
        return true;
55
    }
56

57
    return false;
58
  }
59
};