nt end [start,end]起始位置end
返回值： 如果找到k值，则返回第一个该值所在的位置；否则返回-1.
*/
int GetFirstK(int *sortedArray, int k, int start, int end)
{
if (sortedArray == NULL || start < 0 || end < 0 || start > end)
{
return -1;
}
/* 如果在[start,end]范围内，第一个数字是k，则返回start */
if (sortedArray[start] == k)
{
return start;
}
while (start <= end)
{
int middle = start + (end - start) / 2;
/* 如果sortedArray[middle] < k，则k在数组的下半部分，所以start = middle + 1 */
if (sortedArray[middle] < k)
{
start = middle + 1;
}
/* 如果sortedArray[middle] > k，则k在数组的上半部分，所以end = middle - 1 */
else if (sortedArray[middle] > k)
{
end = middle - 1;
}
/* 如果sortedArray[middle] == k，则判断sortedArray[middle-1]是否等于k。
如果sortedArray[middle-1] == k，则第一个k值在前半部分，则end = middle-1。
如果sortedArray[middle-1] != k，则第一个k值就是middle，则返回middle
*/
else
{
if (sortedArray[middle - 1] == k)
{
end = middle - 1;
}
else
{
return middle;
}
}
}
return -1;
}
然后我们用同样的思路在排序数组中找到最后一个k。如果中间数字比k大，那么k只能出现在数组的前半段。如果中间数组比k小，k就只能出现在数组的后半部分。如果中间数字等于k呢？我们需要判断这个k是不是最后一个k，也就是中间数字的下一个数字是不是也等于k。如果下一个数字不是k，则中间数字就是最后一个k了；否则下一轮我们还是要在数组的后半段中去查找。
基于这个思路，我们很容易实现该算法找到最后一个k：
/*
函数名： GetLastK
函数功能： 从一个有序数组sortedArray[start...end]中找到最后一个k值所在的位置。
函数参数： int *sortedArray 有序数组指针
int k 要查找的k值
int start [start,end]的起始start
int end [start,end]的结束end
返回值： 如果k值存在于数组中，返回最后一个k值所在的位置；否则返回-1。
*/
int GetLastK(int *sortedArray, int k, int start, int end)
{
/* 判断参数的合法性 */
if (sortedArray == NULL || start < 0 || end < 0 || start > end)
{
return -1;
}
/* 如果最后一个数是k，则返回end */
if (sortedArray[end] == k)
{
return end;
}
while (start <= end)
{
int middle = start + (end - start) / 2;
/* 如果sortedArray[middle]小于k，则k将出现在数组的后半段，则start = middle + 1 */
if (sortedArray[middle] < k)
{
start = middle + 1;
}
/* 如果sortedArray[middle]大于k，则k将出现在数组的后半段，则end = middle - 1 */
else if (sortedArray[middle] > k)
{
end = middle - 1;
}
/* 如果sortedArray[middle] == k，则判断sortedArray[middle+1]是否等于k。
如果sortedArray[middle+1] == k，则最后一个k值在后半段，则start = middle + 1。
如果sortedArray[middle+1] != k，则最后一个k值就是middle，则返回middle。
*/
else
{
if (sortedArray[middle + 1] == k)
{
start = middle + 1;
}
else
{
return middle;
}
}
}
return -1;
}
void Test(const char *testName, int *sortedArray, int length, int k, int expectedCount)
{
cout << testName << " : ";
if (GetNumberOfK(sortedArray, length, k) == expectedCount)
{
cout << "Passed." << endl;
}
else
{
cout << "Failed." << endl;
}
}
int main()
{
int sortedArray1[] = {1, 2, 3, 3, 3, 3, 4, 5};
Test("Test1", sortedArray1, sizeof(sortedArray1) / sizeof(int), 3, 4);
int sortedArray2[] = {3, 3, 3, 3, 4, 5};
Test("Test2", sortedArray2, sizeof(sortedArray2) / sizeof(int), 3, 4);
int sortedArray3[] = {1, 2, 3, 3, 3, 3};
Test("Test3", sortedArray3, sizeof(sortedArray3) / sizeof(int), 3, 4);
int sortedArray4[] = {1, 3, 3, 3, 3, 4, 5};
Test("Test4", sortedArray4, sizeof(sortedArray4) / sizeof(int), 2, 0);
int sortedArray5[] = {1, 3, 3, 3, 3, 4, 5};
Test("Test5", sortedArray5, sizeof(sortedArray5) / sizeof(int), 0, 0);
int sortedArray6[] = {1, 3, 3, 3, 3, 4, 5};
Test("Test6", sortedArray6, sizeof(sortedArray6) / sizeof(int), 6, 0);
int sortedArray7[] = {3, 3, 3, 3};
Test("Test7", sortedArray7, sizeof(sortedArray7) / sizeof(int), 3, 4);
int sortedArray8[] = {3, 3, 3, 3};
Test("Test8", sortedArray8, sizeof(sortedArray8) / sizeof(int), 4, 0);
int sortedArray9[] = {3};
Test("Test9", sortedArray9, sizeof(sortedArray9) / sizeof(int), 3, 1);
int sortedArray10[] = {3};
Test("Test10", sortedArray10, sizeof(sortedArray10) / sizeof(int), 4, 0);
Test("Test11", NULL, 0, 0, 0);
}