Given an array of integers sorted in ascending order, 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]. 

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int flag = 0;
    *returnSize = 2;
    int *res = (int*)malloc(sizeof(int)*2);
    res[0] = res[1] = -1;
    for (int i = 0;i < numsSize;i++) {
        if (nums[i] == target) {
            if (flag) {
                res[1] = i;
            } else {
                res[0] = res[1] = i;   
            }
            flag = 1;
        }
    }
    return res;
}

二分法

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int * array = calloc(*returnSize, sizeof(int));
    int start = 0;
    int end = numsSize - 1;
    int mid;
    int first = -1, last = -1;
    //find first target
    while(start+1 < end){
        mid = start + (end - start)/2;
        
        if(nums[mid] >= target)
            end = mid;
        else
            start = mid;
    }
    
    if(nums[start] == target)
        first = start;
    else if(nums[end] == target)
        first = end;
    else{
        array[0] = -1;
        array[1] = -1;
        return array;
    }
    
    start = 0;
    end = numsSize - 1;
    while(start+1 < end){
        mid = start + (end - start)/2;
        
        if(nums[mid] <= target)
            start = mid;
        else
            end = mid;
    }
    
    if(nums[end] == target)
        last = end;
    else if(nums[start] == target)
        last = start;
    else{
        array[0] = -1;
        array[1] = -1;
        return array;
    }
    array[0] = first;
    array[1] = last;
    return array; 
}