Share my simple O(logN) java solution


  • 4
    J
    public class Solution {
        public int search(int[] nums, int target) {
            // find index of min
            int start=0;
            int end=nums.length-1; 
            int minPivot=0;
            while (start<end){
                int mid=(start+end)/2; 
                if(nums[mid]>nums[mid+1]){
                    minPivot=mid+1;
                    break;
                }
                if(nums[mid+1]>nums[end]){
                    start=mid+1;
                }else{
                    end=mid;
                }
            }
            //find target
            int offset=minPivot; 
            start=0;
            end=nums.length-1;
            while (start<=end){
                int mid=(start+end)/2;
                int index=(mid+offset)%nums.length;
                if(nums[index]==target){
                    return index;
                }else if(target>nums[index]){
                    start=mid+1;
                }else{
                    end=mid-1;
                }
            }
            return -1;
        }
    }

Log in to reply
 

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