Iterative Java Two Search Solution


  • 0
    A

    Try not to search for another value that is higher than 'target' to find the upper bound because it would not work if the types are 'float' or 'double'.

    public int[] searchRange(int[] nums, int target) {
            int [] result = new int[2];
            if(nums.length == 0){
                return result;
            }
            // search for the lower bound
            result[0] = searchLeft(nums, target);
            // if the first element is not valid
            if(result[0] < 0 || result[0] >= nums.length || nums[result[0]] != target){
                result[0] = -1;
                result[1] = -1;
                return result;
            }
            // search for the upper bound
            result[1] = searchRight(nums, target);
            return result;
    }
    // search lower bound
    private int searchLeft(int [] nums, int target){
            // start offset of high does not matter
            int low = 0, high = nums.length;
            while(low < high){
                int mid = low + (high - low)/2;
                if(nums[mid] < target){
                    low = mid + 1;
                }
                else{
                    high = mid;
                }
            }
            return low;
    }
    // search upper bound
    private int searchRight(int [] nums, int target){
            int low = 0; // caution: , high = nums.length;
            // since high is returned
            // will cause Exception if -1 is not set
            int high = nums.length - 1; 
            while(low < high){
                // caution
                //int mid = low + (high - low)/2;
                int mid = low + (high - low)/2 + 1;
                if(nums[mid] > target){
                    high = mid - 1;
                }
                else{
                    low = mid;
                }
            }
            return high;
    }
    

    There are some general binary search problems that need to be examined:

    1. Sorted Array, No duplicates
    • Loop condition should be while(low <= high). If the equal sign is missing, then the programs runs in an infinite loop.
    • Lower Bound: low = mid + 1.
    • Upper Bound: high = mid - 1.
    public int binarySearchStandard(int[] num, int target){
        int start = 0;
        int end = num.length - 1;
        while(start <= end){ 
            int mid = start + ((end - start) >> 1);
            if(num[mid] == target)
                return mid;
            else if(num[mid] > target){
                end = mid - 1; 
            }
            else{
                start = mid + 1; 
            }
        }
        return -1;
    }
    
    1. Sorted Array, Contain Duplicates, Search Lower Bound
    • Loop Condition: while(low + 1 < high). When the loop ends, the low and high mush be one space apart.
    public int binarySearchMinimumIndex(int[] num, int target){
        int start = 0;
        int end = num.length - 1;
        while(start + 1 < end){ 
            int mid = start + ((end - start) >> 1);
            if(num[mid] >= target){ 
                end = mid;
            }
            else{
                start = mid + 1; 
            }
        }
        if(num[start] == target) 
            return start;
        else if(num[end] == target)
            return end;
        else
            return -1;
    }
    
    1. Sorted Array, Contains Duplicates, Search Upper Bound
    public int binarySearchMaximumIndex(int[] num, int target){
        int start = 0;
        int end = num.length - 1;
        while(start + 1 < end){ 
            int mid = start + ((end - start) >> 1);
            if(num[mid] <= target){ 
                start = mid;
            }
            else{
                end = mid - 1; 
            }
        }
        if(num[end] == target)
            return end;
        else if(num[start] == target)
            return start;
        else
            return -1;
    }
    

Log in to reply
 

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