Java Solution Big(o) log(n)


  • 0
    Y
    public class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;
        while(high>low){
            int middle = (low+high)/2;
            int mid_right = (middle+high)/2;
            int mid_left = (low+middle)/2;
            if(nums[middle]==nums[low]){
                if(nums[middle]==target){
                    return middle;
                }
            }
            else if(nums[middle]>nums[low]){//左半边是sorted,rotate部分在右半边
                if(target<nums[low]||target>nums[middle]){
                    if(nums[mid_right]==target){
                        return mid_right;
                    }
                    else if(nums[mid_right]<target){
                        middle = mid_right + 1;
                    }
                    else if(nums[mid_right]>target){
                        high = mid_right - 1;
                    }
                    //binary search 右半边
                }
                else{
                    high = middle - 1;//search 左半边
                }
            }
            else if(nums[middle]<nums[low]){//右边是sorted
                if(target<nums[middle]||target>nums[high]){
                    if(nums[mid_left]==target){
                        return mid_left;
                    }
                    else if(nums[mid_left]<target){
                        low = mid_right + 1;
                    }
                    else if(nums[mid_left]>target){
                        middle = mid_right - 1;
                    }
                    //binary search 左半边
                }
                else{
                    low = middle + 1;//search 右半边
                }
            }
        }
        
        return -1;
        
    }
    

    }


Log in to reply
 

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