2.7 Search for a range

Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Example

Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Steps

1. Look for start by binary search
2. Let start = start, look for end by binary search

Code Example

public int[] searchRange(int[] A, int target) {
    int rst[] = new int[2];

    if (A==null || A.length ==0) {
        rst[0] = -1;
        rst[1] = -1;
        return rst;
    }

    //look for start
    int start = 0;
    int end = A.length-1;

    while(start + 1 < end) {
        int mid = (start+end)/2;

        // looking for start
        // when target = A[mid]
        // move end to mid, to look for 1st one
        if (target > A[mid]) {
            start = mid;
        }else{
            end = mid;
        }
    }

    // check start location
    // use else if to check start first
    // if target = start, end is not checked
    if (A[start] == target) {
        rst[0] = start;
    }else if (A[end] == target){
        rst[0] = end;
    }else{
        rst[0] = -1;
        rst[1] = -1;
        return rst;
    }

    // loop for end
    // start = start
    end = A.length-1;

    while(start + 1< end) {
        int mid = (start+end)/2;

        // look for end here
        // if start = 
        if (target>= A[mid]) {
            start = mid;
        }else{
            end = mid;
        }
    }

    // check end location
    // use else if to check end first, if end == target
    // start will be skipped
    if (A[end] == target) {
        rst[1] = end;
    }else if (A[start] == target) {
        rst[1] = start;
    }else{
        // if start is set and end not found
        // then end = start (only one number in range)
        rst[1] = rst[0];
    }

    return rst;
}

Common Mistakes

1. When search for end and not found, forget to set end = start (when range = 1)
2. When confirming exact value of start or end, when look for start, check start first; when look for end, check end first.

    // this is an mistack example
    // check start location, if check end first in else if, 
    // when start = end, start will be overwritten by end
    if (A[end] == target) {
        rst[0] = end;
    }else if (A[start] == target){
        rst[0] = start;
    }else{
        rst[0] = -1;
        rst[1] = -1;
        return rst;
    }