Java solution with Big(O)log(n)


  • -3
    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.