程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二分法計算有序數組中數字出現的次數

二分法計算有序數組中數字出現的次數

編輯：C++入門知識

二分法計算有序數組中數字出現的次數

1. 問題描述

　　在給定的一個已經排好序的數組中，找出指定數字出現的次數。例如數組[1,2,3,4,4,4,4,6,8,9]中4出現的次數為4次。

2. 思路與方法

　　此問題可以在二分法的基礎上進行改進。假設數組a為遞增的數列，需要查找的數字為num，可以分別查找num在數組a中出現的起始位置和最後一次的位置，通過二者的差計算出數字num在數組a中出現的次數。
　　c++代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

//查找指定數字在有序數組中出現的次數，isLeft標記最左和最右
int FindCntofNum(int a[],int len, int num, bool isLeft)
{
    int left = 0, right = len -1;

    int pos,mid;

    while(left <= right)//二分查找
    {
        mid = (left + right)/2;

        if( a[mid] < num )
        {
            left = mid +1;
        }
        else if(a[mid] > num)
        {
            right = mid -1;
        }
        else
        {
            pos = mid;

            if(isLeft)//查找最左值
            {
                right = mid -1;
            }
            else//查找最右值
            {
                left = mid +1;
            }
        }
    }
    return pos;//返回最終查找到的位置
}

int main()
{
    int a[10] = { 1,2,3,4,4,4,4,6,8,9};

    int left , right, dst = 4;

    left = FindCntofNum(a,10,4,true);
    right = FindCntofNum(a,10,4,false);

    printf("count of number %d : %d\n",dst,right - left+1);

    return 0;
}