2 concise Java Solution: iterative and recursive


  • 0
    // version 1: iterative -> compare nums[left] and nums[mid] to narrow the range
    public class Solution {
        public boolean search(int[] nums, int target) {
            int low=0, high=nums.length-1;
            while(low<=high){
                int mid=high+low>>>1;
                if(nums[mid]==target) return true;
                if(nums[low]<nums[mid]){
                    if(nums[low]<=target && target<nums[mid]) high=mid-1;
                    else low=mid+1;
                }else if(nums[low]>nums[mid]){
                    if(target>=nums[low] || target<nums[mid]) high=mid-1;
                    else low=mid+1;
                }else{
                    low++;
                }
            }
            return false;
        }
    }
    
    
    // version 2: recursive -> compare nums[mid] with nums[left] and nums[right] separately 
    public class Solution {
        public boolean search(int[] nums, int target) {
            return search(nums, target, 0, nums.length-1);    
        }
        
        public boolean search(int[] nums, int target, int low, int high){
            if(low>high) return false;
            int mid = low+high>>>1;
            if(nums[mid]==target) return true;
            if(nums[low]==nums[mid] && nums[mid]==nums[high])
                return search(nums, target, low+1, mid-1) || search(nums, target, mid+1, high-1);
            if(nums[low]==nums[mid])
                return search(nums, target, mid+1, high);
            if(nums[mid]==nums[high])
                return search(nums, target, low, mid-1);
            if(nums[mid]<=nums[high]){
                if(nums[mid]<target && target<=nums[high]) 
                    return search(nums, target, mid+1, high);
                else
                    return search(nums, target, low, mid-1);
            }else{
                if(nums[low]<=target && target<nums[mid])
                    return search(nums, target, low, mid-1);
                else
                   return search(nums, target, mid+1, high); 
            }
            
        }
    }

Log in to reply
 

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