13518219792
34. Search for a Range
成都创新互联2013年开创至今，先为饶平等服务建站，饶平等地企业，进行企业商务咨询服务。为饶平企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
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].
题意：
根据给定的排序的整数数组和给定值，查找给定值的起始位置和终止位置。如果查找不到指定值则返回起始位置和终止位置都为-1。
处理：
1）在给定的数组中查找给定值，如果给定值存在，则返回第一次出现的位置；否则返回－1.
2）若返回－1，则返回起始和终止都为－1的数组；否则，分别前向和后向查找起始和终止位置，返回起始终止位置数组。
查找指定值使用递归进行查找。
1）如果下标中间值和起始下标和终止下标一致，且当前值不是指定值，则返回－1.
2）如果找到指定值则返回下标，否则，返回－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;
}
