Java solution in O(logn) time using Binary Search


  • 0
    G
    class Solution {
        public int search(int[] nums, int target) {
            if(nums == null || nums.length == 0)
                return -1;
            
            int pivot = findPivot(nums, 0, nums.length-1);
            
            if(pivot == -1)
                return binarySearch(nums, 0, nums.length-1, target);
            
            if(nums[pivot] == target)
                return pivot;
            
            if(nums[0] <= target)
                return binarySearch(nums, 0, pivot-1, target);
            
            return binarySearch(nums, pivot+1, nums.length-1, target);
        }
        
        
        private int findPivot(int[] arr, int low, int high)
        {
            if(high < low)
                return -1;
            
            if(high == low)
                return low;
            
            int mid = low + (high - low)/2;
            if(mid < high && arr[mid] > arr[mid + 1])
                return mid;
            
            if(mid > low && arr[mid] < arr[mid - 1])
                return mid-1;
            
            if(arr[low] >= arr[mid])
                return findPivot(arr, low, mid-1);
            return findPivot(arr, mid+1, high);
        }
        
        
        private int binarySearch(int[] arr, int low, int high, int key)
        {
            if(high < low)
                return -1;
            
            int mid = low + (high - low)/2;
            if(arr[mid] == key)
                return mid;
            if(key > arr[mid])
                return binarySearch(arr, mid+1, high, key);
            
            return binarySearch(arr, low, mid-1, key);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.