/*************************************************************************
> File Name: 36_NumberOfKey.c
> Author: Juntaran
> Mail: [email protected]
> Created Time: 2016年09月03日 星期六 09时32分10秒
************************************************************************/ #include <stdio.h> // 寻找第一个Key的下标
int GetFirstKey(int* nums, int length, int key, int left, int right)
{
if (nums==NULL || length<= || left>right)
return -; int middle = (left + right) / ;
if (key == nums[middle])
{
if ((middle> && nums[middle-]!=key) || middle==)
return middle;
else
right = middle - ;
}
else if (key > nums[middle])
left = middle + ;
else
right = middle - ; return GetFirstKey(nums, length, key, left, right);
} // 寻找最后一个Key的下标
int GetLastKey(int* nums, int length, int key, int left, int right)
{
if (nums==NULL || length<= || left>right)
return -; int middle = (left + right) / ;
if (key == nums[middle])
{
if ((middle> && nums[middle+]!=key && middle<length) || middle==length-)
return middle;
else
left = middle + ;
}
else if (key > nums[middle])
left = middle + ;
else
right = middle - ; return GetLastKey(nums, length, key, left, right);
} int GetNumberOfKey(int* nums, int length, int key)
{
int count = ;
if (nums==NULL || length<=)
return ; int first = GetFirstKey(nums, length, key, , length-);
int last = GetLastKey( nums, length, key, , length-); if (first>= && last>=)
count = last - first + ; printf("count is %d\n", count);
return count;
} int main()
{
int nums[] = {, , , , , , , };
int length = ;
int key = ; GetNumberOfKey(nums, length, key);
}