Binary Search


  • 0
    public int findPeakElement(int[] nums) {
            int start=-1,end=nums.length;
            int mid=start+(end-start)/2;
            if(nums.length==1){
                return 0;
            }
            if(nums.length==2){
                if(nums[0]>nums[1]){
                    return 0;
                }else{
                    return 1;
                }
            }
            while(!((nums[mid+1]<nums[mid])&&(nums[mid]>nums[mid-1]))){
                if(nums[mid+1]>nums[mid]){
                    start=mid;
                    mid=start+(end-start)/2;//in normal way, odd get exactly mid and even get the smaller mid
                    if(mid+1==nums.length){
                        return mid;
                    }
                }else{
                    end=mid;
                    mid=start+(end-start+1)/2;//This "+1" is to make odd still exactly get mid and even get the bigger mid
                    if(mid-1==-1){
                        return mid;
                    }
                }
            }
            return mid;
        }
    

Log in to reply
 

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