Competitive_Programming/LeetCode/Full_List/33.cpp at master · Ravi-Maurya/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, h = n-1;
        while(l<=h){
            int mid = (l+h)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[l]<=nums[mid]){
                if(nums[l]<=target && target<=nums[mid])
                    h = mid-1;
                else
                    l = mid+1;
            }
            else{
                if(nums[mid]<=target && target<=nums[h])
                    l = mid+1;
                else
                    h = mid-1;
            }
        }
        return -1;
    }
};


class Solution {
public:
    int findPivot(vector<int> & nums) {
        int l = 0 , h = nums.size()-1;
        while(l < h) {
            int m = (l+h)/2;
            if( m < h && nums[m] > nums[m+1])
                return m;
            else if( l < m && nums[m-1] > nums[m])
                return m-1;
            else if( nums[l] < nums[m] )
                l = m+1;
            else{
                 h = m-1;
            }
        }
        return -1;
    }

    int binsrch(vector<int>& nums,int l, int h, int target) {
       int m;
        while(l <= h) {
            m = (l +h)/2;
            if(nums[m] == target)
                return m;
            if(nums[m] > target)
                h = m - 1;
            if(nums[m] < target)
                l = m + 1;
        }
        return -1;
    }
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 0) return -1;
        int pivot =  findPivot(nums);
        if(pivot == -1)
            return binsrch(nums,0,n-1,target);
        else if( nums[pivot] == target)
            return pivot;
        else if(nums[0] > target)
            return binsrch(nums,pivot+1,n-1,target);
        else
            return binsrch(nums,0,pivot-1,target);
        return -1;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0)
            return -1;
        if(n==1){
            if(target==nums[0])
                return 0;
            else
                return -1;
        }
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            else if (nums[mid] > nums[right]) {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else
                right--;
        }
        return -1;
    }
};