数字在排序数组中出现的起始索引号
来源：程序员人生 发布时间：2014-09-03 12:32:27 阅读次数：3163次
题目如下：
给定一个升序的整数数组，查找某一个值在数组中出现的索引号，例如，输入数组2，3，3，4，4，5；查找的数是3，则返回1,2。时间复杂度要求为O（logN）。
初次拿到这个题目可以立即想到用二分查找来做，先比较中间的数和要查找的数，如果关键字（要查找的数）小于中间的数，那么在数组的左半部分继续查找，如果关键字大于中间的数，那么在数组的右半部分继续查找，如果关键字和中间的数相等，那么先比较中间数字的前一个数字是否和关键字相等，如果相等，继续用关键字和前一个数字的前一个数字比较，如果不等，那么当前数字就是要查找的数字，其所在的索引就是第一次出现的地方。对于结束的索引，可以用类似的方法来做，先比较中间数字的后一个数字是否和关键字相等，如果相等，继续用关键字和后一个数字的后一个数字比较，如果不等，那么当前数字就是要查找的数字，其所在的索引就是最后一次出现的地方。但是这样做，最坏的情况下，时间复杂度会退化为O（N），即当数组是同一个数的时候。所以这种方法不是时间上最优的。
其实，本题目是二分查找的变种，我们可以分为两步来做，第一步，求得该数字第一次出现的索引，第二步，求得该数字最后一次出现的索引。
首先来看第一次出现的索引怎么来求，首先比较中间的数和要查找的数，如果关键字（要查找的数）小于中间的数，那么在数组的左半部分继续查找，如果关键字大于中间的数，那么在数组的右半部分继续查找，如果关键字和中间的数相等，那么比较中间数字的前一个数字是否和关键字相等，如果不相等，那么当前的中间索引就是第一次出现的索引，如果相等，那么继续在前半部分查找。具体的实现代码如下：
//寻找开始索引
int GetFirstTarget(int A[], int n, int target,int nStart,int nEnd)
{
if (nStart > nEnd)
{
return -1;
}
//中间索引
int nMid = nStart + ( (nEnd-nStart) >> 1);
int nMidData = A[nMid];
while (nStart <= nEnd)
{
if (target > nMidData)
{
nStart = nMid+1;
}
else if (target < nMidData)
{
nEnd = nMid-1;
}
else if (target == nMidData)
{
if ((target != A[nMid-1] && nMid > 0) || nMid == 0)
{
return nMid;
}
else
nEnd = nMid-1;
}
//更新中间值得索引和值
nMid = nStart + ( (nEnd-nStart) >> 1);
nMidData = A[nMid];
}
return -1;
}
寻找最后一次出现的索引也可以用类似的思路来做：首先比较中间的数和要查找的数，如果关键字（要查找的数）小于中间的数，那么在数组的左半部分继续查找，如果关键字大于中间的数，那么在数组的右半部分继续查找，如果关键字和中间的数相等，那么比较中间数字的
后一个数字是否和关键字相等，如果不相等，那么当前的中间索引就是
最后一次出现的索引，如果相等，那么继续在
后半部分查找。寻找第一个索引和最后一个索引的具体差别可以注意红色字体的字眼，具体的实现代码如下：
//寻找结束索引
int GetSecondTarget(int A[], int n, int target,int nStart,int nEnd)
{
if (nStart > nEnd)
{
return -1;
}
//中间索引
int nMid = nStart + ( (nEnd-nStart) >> 1);
int nMidData = A[nMid];
while (nStart <= nEnd)
{
if (target > nMidData)
{
nStart = nMid+1;
}
else if (target < nMidData)
{
nEnd = nMid-1;
}
else if (target == nMidData)
{
if ((target != A[nMid+1] && nMid < n) || nMid == n-1)
{
return nMid;
}
else
nStart = nMid+1;
}
//更新中间值得索引和值
nMid = nStart + ( (nEnd-nStart) >> 1);
nMidData = A[nMid];
}
return -1;
}
最后就是主功能函数进行调用了，其代码如下：
vector<int> searchRange(int A[], int n, int target)
{
std::vector<int> vecIndex;
vecIndex.resize(2);
vecIndex[0] = -1;
vecIndex[1] = -1;
if (A == NULL || n <= 0)
{
return vecIndex;
}
vecIndex[0] = GetFirstTarget(A,n,target,0,n-1);
vecIndex[1] = GetSecondTarget(A,n,target,0,n-1);
return vecIndex;
}
两次查找的时间复杂度都是O（logN），所以总的时间复杂度就是O（logN）。
最后，这个题目还有另外一个变种就是数字在排序数组中出现的次数
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
