Leetcode: Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

public int[] searchRange(int[] A, int target) {

        int i=0;

        int j=A.length-1;

        int[] results={-1,-1};

        //the idea is to put the lower bound in i

        while(i<j){

            int mid=i+(j-i)/2;

            if(target<=A[mid])

                j=mid;

            else

                i=mid+1;

        }

        if(A[i]==target) 

            results[0]=i;

        else

            return results; 

        i=0;

        j=A.length;

        //the idea is to put the upper bound in j-1

        while(i<j){

            int mid=i+(j-i)/2;

            if(target>=A[mid])

                i=mid+1;

            else

                j=mid;

        }

        results[1]=j-1;

        return results;

    }

Code from http://www.darrensunny.me/leetcode-search-for-a-range/

public int[] searchRange(int[] A, int target) {

    int[] result = {-1, -1};

    int n = A.length;

    if (A == null || n == 0)

        return result;

    // Find one target first

    int separator = -1;         // The index of one of several appearances of target

    int left = 0, right = n-1;

    while (left <= right) {

        int middle = (left+right) / 2;

        if (A[middle] > target) {   // target must be at the left half

            right = middle - 1;

        } else if (A[middle] < target) {    // target must be at the right half

            left = middle + 1;

        } else {            // Find one target

            separator = middle;

            break;

        }

    }

    if (separator == -1)        // No target exists

        return result;

 

    // Find the starting index within A[0...separator]

    left = 0;

    right = separator;

    while (left <= right) {

        int middle = (left+right) / 2;

        if (A[middle] == target)    // right will end up at right before the starting index

            right = middle - 1;

        else        // A[middle]<target; the starting index should be within [middle+1,right]

            left = middle + 1;

    }   // out of loop; left = right - 1, i.e. the starting index

    result[0] = left;   // Save the starting index in result[0]

 

    // Find the ending index within A[separator+1...n-1]

    left = separator;

    right = n - 1;

    while (left <= right) {

        int middle = (left+right) / 2;

        if (A[middle] == target)    // left will end up at right after the ending index

            left = middle + 1;

        else        // A[middle]>target; the starting index should be within [left, middle-1]

            right = middle - 1;

    }   // out of loop; right = left + 1, i.e. the ending index

    result[1] = right;  // Save the ending index in result[1]

 

    return result;

}

Also check http://zhaohongze.com/wordpress/2014/01/05/leetcode-search-for-a-range/
Read full article from 西小瓜: Leetcode: Search for a Range