1 /************************************************************************* 2     > File Name: 36_NumberOfKey.c 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年09月03日 星期六 09时32分10秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 10 // 寻找第一个Key的下标11 int GetFirstKey(int* nums, int length, int key, int left, int right)12 {13     if (nums==NULL || length<=0 || left>right)14         return -1;15     16     int middle = (left + right) / 2;17     if (key == nums[middle])18     {19         if ((middle>0 && nums[middle-1]!=key) || middle==0)20             return middle;21         else22             right = middle - 1;23     }24     else if (key > nums[middle])25         left = middle + 1;26     else27         right = middle - 1;28     29     return GetFirstKey(nums, length, key, left, right);30 }31 32 // 寻找最后一个Key的下标33 int GetLastKey(int* nums, int length, int key, int left, int right)34 {35     if (nums==NULL || length<=0 || left>right)36         return -1;37     38     int middle = (left + right) / 2;39     if (key == nums[middle])40     {41         if ((middle>0 && nums[middle+1]!=key && middle<length) || middle==length-1)42             return middle;43         else44             left = middle + 1;45     }46     else if (key > nums[middle])47         left = middle + 1;48     else49         right = middle - 1;50     51     return GetLastKey(nums, length, key, left, right);52 }53 54 int GetNumberOfKey(int* nums, int length, int key)55 {56     int count = 0;57     if (nums==NULL || length<=0)58         return 0;59     60     int first = GetFirstKey(nums, length, key, 0, length-1);61     int last  = GetLastKey( nums, length, key, 0, length-1);62     63     if (first>=0 && last>=0)64         count = last - first + 1;65     66     printf("count is %d\n", count);67     return count;68 }69 70 int main()71 {72     int nums[] = {1, 2, 3, 3, 3, 3, 4, 5};73     int length = 8;74     int key = 3;75     76     GetNumberOfKey(nums, length, key);77 }