#includebool g_bRightNumber = false;void MyGetNumberHelp(int* data, int start, int end, int** first, int** last, int k);int MyGetNumber(int* data, int length, int k) { g_bRightNumber = false; if(data == NULL || length <=0) return 0; int** first = &data; int* lastn = data+length-1; int** last = &lastn; MyGetNumberHelp(data, 0, length-1, first, last, k); int number = *last-*first+1; delete first; delete last; return g_bRightNumber ? number : 0;}void MyGetNumberHelp(int* data, int start, int end, int** first, int** last, int k) { if(start > end) return; int mid = (start+end) >> 1; if(data[mid] > k) MyGetNumberHelp(data, start, mid-1, first, last, k); else if(data[mid] < k) MyGetNumberHelp(data, mid+1, end, first, last, k); else { if(!g_bRightNumber) g_bRightNumber = true; if(mid>0 && mid<*last-data) { if(data[mid-1] < k) { *first = &data[mid]; MyGetNumberHelp(data, start, mid-1, first, last, k); } else if(data[mid+1] > k) { *last = &data[mid]; MyGetNumberHelp(data, mid+1, end, first, last, k); } else { MyGetNumberHelp(data, mid+1, end, first, last, k); MyGetNumberHelp(data, start, mid-1, first, last, k); } } }}//=========================hht's=============================int GetFirstK(int* data, int length, int k, int start, int end) { if(start > end) return -1; int middleIndex = (start+end) >> 1; int middleData = data[middleIndex]; if(middleData == k) { if((middleIndex > 0 && data[middleIndex-1] != k) || middleIndex == 0) return middleIndex; else end = middleIndex-1; } else if(middleData > k) end = middleIndex - 1; else start = middleIndex + 1; return GetFirstK(data, length, k, start, end);}int GetLastK(int* data, int length, int k, int start, int end) { if(start > end) return -1; int middleIndex = (start+end) >> 1; int middleData = data[middleIndex]; if(middleData == k) { if((middleIndex < length-1 && data[middleIndex+1] != k) || middleIndex == length-1) return middleIndex; else start = middleIndex + 1; } else if(middleData < k) start = middleIndex + 1; else end = middleIndex - 1; return GetLastK(data, length, k, start, end);}int GetNumberOfK(int* data, int length, int k) { int number = 0; if(data != NULL && length >= 0) { int first = GetFirstK(data, length, k, 0, length-1); int last = GetLastK(data, length, k, 0, length-1); if(first > -1 && last > -1) number = last-first+1; } return number;}// ====================测试代码====================void Test(const char* testName, int data[], int length, int k, int expected){ if(testName != NULL) printf("%s begins: ", testName);// int result = MyGetNumber(data, length, k); int result = GetNumberOfK(data, length, k); if(result == expected) printf("Passed.\n"); else printf("Failed.\n");}// 查找的数字出现在数组的中间void Test1(){ int data[] = {1, 2, 3, 3, 3, 3, 4, 5}; Test("Test1", data, sizeof(data) / sizeof(int), 3, 4);}// 查找的数组出现在数组的开头void Test2(){ int data[] = {3, 3, 3, 3, 4, 5}; Test("Test2", data, sizeof(data) / sizeof(int), 3, 4);}// 查找的数组出现在数组的结尾void Test3(){ int data[] = {1, 2, 3, 3, 3, 3}; Test("Test3", data, sizeof(data) / sizeof(int), 3, 4);}// 查找的数字不存在void Test4(){ int data[] = {1, 3, 3, 3, 3, 4, 5}; Test("Test4", data, sizeof(data) / sizeof(int), 2, 0);}// 查找的数字比第一个数字还小，不存在void Test5(){ int data[] = {1, 3, 3, 3, 3, 4, 5}; Test("Test5", data, sizeof(data) / sizeof(int), 0, 0);}// 查找的数字比最后一个数字还大，不存在void Test6(){ int data[] = {1, 3, 3, 3, 3, 4, 5}; Test("Test6", data, sizeof(data) / sizeof(int), 6, 0);}// 数组中的数字从头到尾都是查找的数字void Test7(){ int data[] = {3, 3, 3, 3}; Test("Test7", data, sizeof(data) / sizeof(int), 3, 4);}// 数组中的数字从头到尾只有一个重复的数字，不是查找的数字void Test8(){ int data[] = {3, 3, 3, 3}; Test("Test8", data, sizeof(data) / sizeof(int), 4, 0);}// 数组中只有一个数字，是查找的数字void Test9(){ int data[] = {3}; Test("Test9", data, sizeof(data) / sizeof(int), 3, 1);}// 数组中只有一个数字，不是查找的数字void Test10(){ int data[] = {3}; Test("Test10", data, sizeof(data) / sizeof(int), 4, 0);}// 鲁棒性测试，数组空指针void Test11(){ Test("Test11", NULL, 0, 0, 0);}int main(int argc, char* argv[]){ Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); Test8(); Test9(); Test10(); Test11(); return 0;}