[数据结构与算法]数字在升序数组中出现的次数

1.思路：在有序数组中查找所要查找的数，使用折半查找法效率非常高，设一个数组成员={1，2，3，3，3，3，3，3，4，5}，若想要得到数组中3所出现的次数，可以用采用（查找数右下标—查找数左下标）+1的方法实现，如上数组中出现3的个数：（7-2）+1，函数在调用期间，return只能返回一个变量，所以需要调用2次函数得到左右下标

2.实现数字在升序数组中出现的次数

#include<stdio.h>
int lin(int* arr, int sz, int k, int flag)
{
    int left = 0, right = sz - 1, mid = 0;    //left为左下标，right为右下标
    while (left <= right)
    {
        mid = left + (right - left) / 2;    //mid为中间下标
        if (arr[mid] > k)
        {
            right = mid - 1;
        }
        else if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else    //中间下标与查找数相等
        {
            if (flag == 0)    
            {
                if (mid == left || arr[mid - 1] != k) //判断mid是否为查找数左下标
                {
                    return mid;
                }
                else
                {
                    right = mid - 1;
                }
            }
            else    //查找数右下标返回值
            {
                if (mid == right || arr[mid + 1] != k) //判断mid是否为查找数右下标
                {
                    return mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
        }
    }
    return -1;    //查找数不存在则返回-1
}
int li(int* arr, int sz, int k) {
    if (sz == 0)
    {
        return 0;
    }
    int left = lin(arr, sz, k, 0);    //设查找数左下标进入判断条件时的条件数为0
    int right = lin(arr, sz, k, 1);   //设查找数左下标进入判断条件时的条件数为1 
    if (left == -1 && right == -1)    
    {
        return 0;
    }
    return right - left + 1;    //（查找数右下标-查找数左下标）+1
}
int main()
{
    int k = 0;
	int arr[] = { 1,2,3,3,3,3,3,3,4,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
    printf("请输入需要查找的数字:");
    scanf("%d", &k);
    int sum=li(arr, sz, k);
    if (sum == 0)    
    {
        printf("查找的数不存在");
    }
    else
    {
        printf("数组中所要查找的数共有%d个", sum);
    }
    return 0；
}