Great Example to Illustrate How to Write Correct Binary Search Code


  • 2
    J

    Simple idea,
    Difficult to write correct code

    Idea is simple:

    1. find start index
    2. find end index
    3. return [start, end]

    The Subtle Part:
    How to define mid-point in binary search?
    How to update two pointers?
    What is the while loop condition?

    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            // both (i+j)/2 and (i+j)/2 + 1 could be interpreted as mid-point
            // in (i+j)/2     as mid-point cases, use lo = mid+1, hi = mid to avoid infinite loop
            // in (i+j)/2 + 1 as mid-point cases, use hi = mid-1, lo = mid to avoid infinite loop
            
            
            // search for start point
            int i = 0, j = nums.length-1;
            while(i != j){
                // loop invariant : start point must be in [i,j]
                int mid = (i+j)/2;
                if(nums[mid] >= target) j = mid;
                else i = mid + 1;
            }
            
            int start = i;
            if(nums[i] != target) return new int[]{-1,-1};
            
            // search for end point
            j = nums.length-1;
            while(i != j){
                // loop invariant : end point must be in [i,j]
                int mid = (i+j)/2 + 1;
                if(nums[mid] > target) j = mid-1;
                else i = mid;
            }
            
            return new int[]{start, j};
            
        }
    }
    

  • 0
    P

    @Jingshi very nice!


Log in to reply
 

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