vaibhav1906

Search in Rotated Sorted Array

Nov 25th, 2021
688
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int search(vector<int>& arr, int target) {
  4.        
  5.        int n = arr.size();
  6.        
  7.        //Binary search to find pivot index
  8.        
  9.         int l = 0, h = n-1;
  10.         //First true for arr[0]-arr[m]>0
  11.         while(l<h){
  12.             int m = l + (h-l)/2;
  13.             if(arr[0]-arr[m]>0){
  14.                 h = m;
  15.             }
  16.             else{
  17.                 l = m+1;
  18.             }
  19.         }
  20.        
  21.         int pivot = l;
  22.        
  23.         //Binary search to search the given target in left sorted array
  24.         l = 0; h = pivot-1;
  25.        
  26.         //First true for arr[m]>=target
  27.        
  28.         while(l<h){
  29.             int m = l + (h-l)/2;
  30.            
  31.             if(arr[m]>=target){
  32.                 h = m;
  33.             }
  34.             else{
  35.                 l = m+1;
  36.             }
  37.            
  38.         }
  39.        
  40.         if(arr[l]==target)return l;
  41.        
  42.         //Binary search to search the given target in right sorted array
  43.        
  44.         l = pivot; h = n-1;
  45.        
  46.         //First true for arr[m]>=target
  47.        
  48.         while(l<h){
  49.             int m = l + (h-l)/2;
  50.            
  51.             if(arr[m]>=target){
  52.                 h = m;
  53.             }
  54.             else{
  55.                 l = m+1;
  56.             }
  57.            
  58.         }
  59.        
  60.         if(arr[l]==target)return l;
  61.        
  62.        
  63.         return -1; //If element is not present at all
  64.        
  65.        
  66.     }
  67. };
RAW Paste Data