數字在排序數組中出現的起始索引號
來源：程序員人生 發布時間：2014-09-03 12:32:27 閱讀次數：3287次
題目如下：
給定一個升序的整數數組，查找某一個值在數組中出現的索引號，例如，輸入數組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）。
最后，這個題目還有另外一個變種就是數字在排序數組中出現的次數
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
