SearchInSortedRotatedArray

import java.util.*;

class Solution {
    public int search(int[] a, int target) {
        
        int l = 0;
        int h = a.length - 1;
        
        while(l<=h){
            int mid = l + (h-l)/2;
            
            if(a[mid] == target)
                return mid;
            if(a[l]<=a[mid]){
                if(target>=a[l] && target<a[mid])
                    h = mid - 1;
                else
                    l = mid + 1;
            }
            if(a[h]>=a[mid]){
                if(target<=a[h] && target>a[mid])
                    l = mid + 1;
                else
                    h = mid - 1;
            }
        }
        return -1;
        
    }
}
// driver class
public class Main{
  public static void main(String args[]){
     Scanner sc = new Scanner(System.in);
     System.out.print("Enter array size: ");
     int n = sc.nextInt();
     System.out.print("Enter array elements: ");
     int arr[] = new int[n];
     for(int i=0;i<n; i++){
        arr[i] = sc.nextInt();
     }
     System.out.print("Enter target element: ");
     int target = sc.nextInt();
     Solution obj = new Solution();
     int index = obj.search(arr, target);
     if(index >-1){
         System.out.print("Index of element is: "+index);
     }
     else{
          System.out.print("element doesn't exist");
     }
  }
}