二分法计算有序数组中数字出现的次数 - c++编程基础

TOP

二分法计算有序数组中数字出现的次数

2015-11-21 01:00:18 来源: 作者: 【大中小】浏览:1次

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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1398 Square Coins（母函数）	下一篇：leetcode 218: The Skyline Probl..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: