Recursive solution for Java


  • 1
    I
    public int search(int[] nums, int target) {
        return binarySearch(0, nums.length - 1, nums, target);
    }
    
    public int binarySearch(int low, int high, int[] nums, int target){
        int mid = (low + high)/2;
        if(nums[mid] == target)
            return mid;
        if(low > high)
            return -1;
            
        if(nums[mid] >= nums[low]){//array between nums[low] and nums[mid] are sorted
            if( nums[low] <= target && target < nums[mid])//target is between nums[low] and nums[mid]
                return binarySearch(low, mid - 1, nums, target);
            else
                return binarySearch(mid + 1, high, nums, target);
        }
        else{//unsorted part of array
            if(nums[mid] < target && target <= nums[high])
                return binarySearch(mid + 1, high, nums, target);
            else
                return binarySearch(low, mid - 1, nums, target);
        }
    }

  • 0
    C

    Similar idea.

    public class Solution {
        public int search(int[] nums, int target) {
            if (nums == null || nums.length == 0) return -1;
            return search(nums, target, 0, nums.length - 1);
        }
        
        private int search(int[] nums, int target, int start, int end) {
            if (start > end) return -1;
            int mid = (start + end) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target && nums[mid] < nums[start] && target > nums[end]) {
                return search(nums, target, start, mid - 1);
            }
            if (nums[mid] < target) return search(nums, target, mid + 1, end);
            if (nums[mid] > target && nums[mid] > nums[end] && target < nums[start]) {
                return search(nums, target, mid + 1, end);
            }
            return search(nums, target, start, mid - 1);
        }
    }

Log in to reply
 

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