Advertisement
Rohit4Pal

Search in Rotated Sorted Array

Jun 30th, 2021
1,029
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.        
  5.         //first we need to find the pivot i.e. a[i]>a[i-1] && a[i]>a[i+1]
  6.         int pivot=findIndexOfPivot(nums);
  7.         cout<<pivot;
  8.        
  9.         int l=binarySearch(nums,0,pivot+1,target);
  10.         int r=binarySearch(nums,pivot+1,nums.size(),target);
  11.        
  12.         return max(l,r);
  13.     }
  14.     int findIndexOfPivot(vector<int> arr){
  15.        
  16.         int start=0,end=arr.size()-1;
  17.         while(start<end){
  18.            
  19.             int mid=start+(end-start)/2;
  20.             if(arr[mid]<arr[0])
  21.                 end=mid-1;
  22.             else    start=mid;
  23.         }
  24.         return start;
  25.     }
  26.     int binarySearch(vector<int> arr,int start,int n,int x){
  27.        
  28.         if(start >= arr.size())
  29.             return -1;
  30.        
  31.         int end=n-1,mid=0;
  32.         while(start<end){
  33.             mid=start+(end-start)/2;
  34.             if(arr[mid]==x)     return mid;
  35.             else if(arr[mid]>x)     end=mid-1;
  36.             else    start=mid+1;
  37.         }
  38.         if(arr[start]==x)   return start;
  39.         return -1;
  40.     }
  41. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement