剑指offer第三十八题：数字在排序数组中出现的次数

1 //============================================================================  2 // Name        : JZ-C-38.cpp  3 // Author      : Laughing_Lz  4 // Version     :  5 // Copyright   : All Right Reserved  6 // Description : 数字在排序数组中出现的次数  7 //============================================================================  8   9 #include 
     
       10 #include 
      
        11 using namespace std; 12  13 int GetFirstK(int* data, int length, int k, int start, int end); 14 int GetLastK(int* data, int length, int k, int start, int end); 15  16 int GetNumberOfK(int* data, int length, int k) { 17     int number = 0; 18  19     if (data != NULL && length > 0) { 20         int first = GetFirstK(data, length, k, 0, length - 1); 21         int last = GetLastK(data, length, k, 0, length - 1); 22  23         if (first > -1 && last > -1) 24             number = last - first + 1; 25     } 26  27     return number; 28 } 29  30 // 找到数组中第一个k的下标。如果数组中不存在k，返回-1 31 int GetFirstK(int* data, int length, int k, int start, int end) { 32     if (start > end) 33         return -1; 34  35     int middleIndex = (start + end) / 2; 36     int middleData = data[middleIndex]; 37  38     if (middleData == k) { 39         if ((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0)// data[middleIndex - 1] != k 以此判断是不是第一个k 40             return middleIndex; 41         else 42             end = middleIndex - 1; 43     } else if (middleData > k) 44         end = middleIndex - 1; 45     else 46         start = middleIndex + 1; 47  48     return GetFirstK(data, length, k, start, end); 49 } 50  51 // 找到数组中最后一个k的下标。如果数组中不存在k，返回-1 52 int GetLastK(int* data, int length, int k, int start, int end) { 53     if (start > end) 54         return -1; 55  56     int middleIndex = (start + end) / 2; 57     int middleData = data[middleIndex]; 58  59     if (middleData == k) { 60         if ((middleIndex < length - 1 && data[middleIndex + 1] != k)//data[middleIndex + 1] != k 以此判断是不是最后一个k 61                 || middleIndex == length - 1) 62             return middleIndex; 63         else 64             start = middleIndex + 1; 65     } else if (middleData < k) 66         start = middleIndex + 1; 67     else 68         end = middleIndex - 1; 69  70     return GetLastK(data, length, k, start, end); 71 } 72  73 // ====================测试代码==================== 74 void Test(char* testName, int data[], int length, int k, int expected) { 75     if (testName != NULL) 76         printf("%s begins: ", testName); 77  78     int result = GetNumberOfK(data, length, k); 79     if (result == expected) 80         printf("Passed.\n"); 81     else 82         printf("Failed.\n"); 83 } 84  85 // 查找的数字出现在数组的中间 86 void Test1() { 87     int data[] = { 1, 2, 3, 3, 3, 3, 4, 5 }; 88     Test("Test1", data, sizeof(data) / sizeof(int), 3, 4); 89 } 90  91 // 查找的数组出现在数组的开头 92 void Test2() { 93     int data[] = { 3, 3, 3, 3, 4, 5 }; 94     Test("Test2", data, sizeof(data) / sizeof(int), 3, 4); 95 } 96  97 // 查找的数组出现在数组的结尾 98 void Test3() { 99     int data[] = { 1, 2, 3, 3, 3, 3 };100     Test("Test3", data, sizeof(data) / sizeof(int), 3, 4);101 }102 103 // 查找的数字不存在104 void Test4() {105     int data[] = { 1, 3, 3, 3, 3, 4, 5 };106     Test("Test4", data, sizeof(data) / sizeof(int), 2, 0);107 }108 109 // 查找的数字比第一个数字还小，不存在110 void Test5() {111     int data[] = { 1, 3, 3, 3, 3, 4, 5 };112     Test("Test5", data, sizeof(data) / sizeof(int), 0, 0);113 }114 115 // 查找的数字比最后一个数字还大，不存在116 void Test6() {117     int data[] = { 1, 3, 3, 3, 3, 4, 5 };118     Test("Test6", data, sizeof(data) / sizeof(int), 6, 0);119 }120 121 // 数组中的数字从头到尾都是查找的数字122 void Test7() {123     int data[] = { 3, 3, 3, 3 };124     Test("Test7", data, sizeof(data) / sizeof(int), 3, 4);125 }126 127 // 数组中的数字从头到尾只有一个重复的数字，不是查找的数字128 void Test8() {129     int data[] = { 3, 3, 3, 3 };130     Test("Test8", data, sizeof(data) / sizeof(int), 4, 0);131 }132 133 // 数组中只有一个数字，是查找的数字134 void Test9() {135     int data[] = { 3 };136     Test("Test9", data, sizeof(data) / sizeof(int), 3, 1);137 }138 139 // 数组中只有一个数字，不是查找的数字140 void Test10() {141     int data[] = { 3 };142     Test("Test10", data, sizeof(data) / sizeof(int), 4, 0);143 }144 145 // 鲁棒性测试，数组空指针146 void Test11() {147     Test("Test11", NULL, 0, 0, 0);148 }149 150 int main(int argc, char** argv) {151     Test1();152     Test2();153     Test3();154     Test4();155     Test5();156     Test6();157     Test7();158     Test8();159     Test9();160     Test10();161     Test11();162 163     return 0;164 }