My AC Java Solution.


  • 1
    S

    is the complexity of the code below O(lgn)?

    public class Solution {
    public boolean search(int[] nums, int target) {
        int n=nums.length;
        if(n==0) return false;
        int start =0; int end = n-1;
        return searchR(start, end, nums, target);
    }
    
    public boolean searchR(int start, int end, int[] nums,int target) {
        while(start<=end)
        {
            int mid=(start+end)/2;
            //find it
            if(nums[mid]==target) return true;
            //left is sorted
            if(nums[start]<nums[mid]) {
                //and target is in left
                if(nums[start]<=target&&nums[mid]>=target) end=mid-1;
                //otherwise, check right
                else return searchR(mid+1,end,nums,target);
            }
            //right is sorted
            else if(nums[start]>nums[mid]) {
                //and target is in right
                if(nums[mid]<=target&&nums[end]>=target) start=mid+1;
                //otherwise check left side
                else return searchR(start, mid-1, nums, target);
            }
            else {
                //start , end and mid are the same, cannot tell, the divide and try again
                return searchR(start, mid-1, nums, target) || searchR(mid+1, end, nums, target);
            }
        }
        return false;
    }
    

    }


Log in to reply
 

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