程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved