[LeetCode]34. Search for a Range

34. 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].

題意：

根據(jù)給定的排序的整數(shù)數(shù)組和給定值，查找給定值的起始位置和終止位置。如果查找不到指定值則返回起始位置和終止位置都為-1。

處理：

1）在給定的數(shù)組中查找給定值，如果給定值存在，則返回第一次出現(xiàn)的位置；否則返回－1.

2）若返回－1，則返回起始和終止都為－1的數(shù)組；否則，分別前向和后向查找起始和終止位置，返回起始終止位置數(shù)組。

查找指定值使用遞歸進(jìn)行查找。

1）如果下標(biāo)中間值和起始下標(biāo)和終止下標(biāo)一致，且當(dāng)前值不是指定值，則返回－1.

2）如果找到指定值則返回下標(biāo)，否則，返回－1

int
findIndex( int *nums, int begin, int end, int target)
{
    int low  = begin;
    int high = end;
    int mid  = ( low + high ) / 2;
    int value = -1; 
    /* 5 7 7 8 8 10*/
    if ( mid == high && low == mid && *(nums + mid) != target )
    {
        return -1;
    }
    if ( *( nums + mid ) < target )
    {
        value = findIndex( nums, mid + 1, high, target );
    }
    else if ( *( nums + mid ) > target )
    {
        value = findIndex( nums, low, mid, target );
    }
    else if ( *( nums + mid ) == target )
    {
        return mid;
    }
    
    return value;
}

/**
 * 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)
{
    int *dest = NULL;
    dest = (int *)malloc(sizeof(int) * 3);
    if ( !dest )
    {
        return NULL;
    }
    
    int mid = findIndex( nums, 0, numsSize - 1, target );
    if ( mid == -1 )
    {
        dest[0] = -1;
        dest[1] = -1;
        dest[2] = '\0';
        *returnSize = 2;
        return dest;
    }
    
    int cnt = mid;
    while ( cnt >= 0 && *( nums + cnt ) == target )
    {
        cnt -= 1;
    }
    
    int index = mid;
    while ( index < numsSize && *( nums + index ) == target )
    {
        index += 1;
    }
    
    dest[0] = cnt + 1;                                                    
    dest[1] = index - 1;
    dest[2] = '\0';
    *returnSize = 2;
    return dest;
}