Share my Java solution, 2 BS with tie-breaking, detailed explanation


  • 0
    M
        public int[] searchRange(int[] nums, int target) {
            int[] result = {-1, -1};
            
            // first binary search finds the lower index of the target
            int st = 0;
            int ed = nums.length - 1;
            while (st < ed) {
                int mid = st + (ed - st) / 2;   // floor function
                if (nums[mid] < target)
                    st = mid + 1;
                else
                    ed = mid;
            }
            
            if (nums[st] == target) {
                // the target exists in the array
                result[0] = st;
                
                // second binary search finds the higher index of the target
                ed = nums.length - 1;
                while (st < ed) {
                    int mid = st + (ed - st + 1) / 2;   // ceiling function
                    if (nums[mid] <= target)
                        st = mid;
                    else
                        ed = mid - 1;
                }
                result[1] = ed;
            }
            
            return result;
        }
    

    My solution is to rewrite traditional binary search so it can break ties and proceed in the direction you want. In the ideal case, we want the 'st' pointer staying on the lower index, and the 'ed' pointer staying on the higher index. We break this problem into two binary search problem, accomplishing this two jobs separately. Therefore, when nums[mid] = target, we shouldn't stop the binary search but reduce our searching range.

    To find the lower index, the range should be maintained as [st, ed), so the shrinking direction should be from the direction of 'ed' (please consider why). The traditional binary search algorithm actually uses a floor function when calculating the 'mid' index. This is what we want for finding the lower index. However, finding higher index is a reverse problem of finding the lower index. Therefore, we need to maintain the range as (st, ed] and rewrite the 'mid' index calculation as a ceiling function.


Log in to reply
 

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