Simple Java O(Logn) Solution- modified Binary Search


  • 0
    S
    //Modified Binary Search - Very Easy to Understand
    //Binary Search for pivot
    //Followed by Binary search for the number in part of array before pivot or part of array after pivot
    
    
    public int search(int[] nums, int target) {
                if(nums.length<=1){
                    if(nums[0]==target)
                        return 0;
                    else
                        return -1;
                }
                int pivot = modifiedBS(nums,0,nums.length-1);
                if(pivot!=-1){
                    if(nums[pivot]==target)
                        return pivot;
                }
                if(pivot == nums.length-1 || pivot==-1)
                    return(BinaySearch(nums,0,nums.length-1,target));
                if(target>=nums[0] && target<=nums[pivot])
                    return(BinaySearch(nums,0,pivot,target));
                else
                    return(BinaySearch(nums,pivot+1,nums.length-1, target));
            }
            
            public int modifiedBS(int[] nums, int start, int end){
                if((end-start)<=1){
                    if(start==end)
                        return -1;
                    else{
                        if(nums[start]>nums[end])
                            return start;
                        else
                            return -1;
                    }
                }
                int mid = start+(end-start)/2;
                if(nums[mid-1]<nums[mid] && nums[mid]<nums[mid+1]){
                    int left = modifiedBS(nums,start,mid);
                    int right = modifiedBS(nums,mid+1,end);
                    if(left!= -1 || right!= -1){
                        if(left!=-1)
                            return left;
                        else
                            return right;
                    }
                    return -1;
                }
                if(nums[mid-1]>nums[mid])
                    return mid-1;
                else
                    return mid;
            }
            
            public int BinaySearch(int[] nums, int start, int end, int num){
                if((end-start)<=1){
                    if(start==end)
                        if(nums[start]==num)
                            return start;
                        else
                            return -1;
                    else{
                        if(nums[start]==num)
                            return start;
                        else if(nums[end]==num)
                            return end;
                        else
                            return -1;
                    }
                }
                int mid = start+(end-start)/2;
                if(nums[mid]>num)
                    return BinaySearch(nums, start,mid-1, num);
                else if(nums[mid]<num)
                    return BinaySearch(nums, mid+1,end, num);
                else
                    return mid;
            }

Log in to reply
 

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