JAVA once clear binary search


  • 0
    Q

    My code may not be very short, but I thought it's clear and easy to understand. The most important fact to realize is that no matter what, at least one half (either low ~mid, mid ~ high) is well sorted. We can use this to solve the problem case by case

        public int search(int[] nums, int target) {
            int low = 0;
            int high = nums.length - 1;
            int mid = low + (high - low)/2;
    
            while(low <= high){
                int midVal = nums[mid];
                if(target == midVal){
                    return mid;
                }
                // whole list is well sorted
                if(midVal < nums[high] && midVal > nums[low]){
                    if(target < midVal){
                        high = mid - 1;
                    }
                    else{
                        low = mid + 1;
                    }
                }
                // right side is sorted
                else if(midVal < nums[low]){
                    if(target < midVal){
                        high = mid - 1;
                    }
                    else{
                        if(nums[high] >= target){
                            low = mid + 1;
                        }
                        else{
                            high = mid - 1;
                        }
                    }
                }
                // left side is sorted
                else{
                    if(target < midVal){
                        if(nums[low] <= target){
                            high = mid - 1;
                        }
                        else{
                            low = mid + 1;
                        }
                    }
                    else{
                        low = mid + 1;
                    }
                }
                mid = low + (high - low)/2;
            }
    
            return -1;
        }
    

Log in to reply
 

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