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].
题意：
根据给定的排序的整数数组和给定值，查找给定值的起始位置和终止位置。如果查找不到指定值则返回起始位置和终止位置都为-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;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
