如果百度上能解决的，我就不会拿这上面来丢人了。

int element_count(const std::vector<int> &set, int e)
{
    int left, right, middle;
    left = 0, right = set.size() - 1;
    int count = 0;

    while (left <= right)
    {
        middle = (left + right) / 2;
        if (set.at(middle) > e)
        {
            right = middle - 1;
        }
        else if (set.at(middle) < e)
        {
            left = middle + 1;
        }
        else
        {
            while (middle - 1 >= 0 && set.at(middle) == set.at(middle - 1)) middle -= 1;
            while (set.at(middle) == set.at(middle + 1))
            {
                middle += 1;
                ++count;
            }
            return ++count;
        }
    }

    return 0;
}

不用给我分,写的时候猛然发觉c++写多了,不会写C了...所以改了一下参数换成了STL的容器...
但是没用STL的特性...我测了一下,应该是没问题的...
判断个数的地方偷懒了,其实可以更高效一些...

如果搜索引擎都解决不了
你认为你遇到了一个人类有史以来从没有人遇到过的新奇算法?

假设
2+2+2你去问搜索引擎,
搜索引擎告诉你
我只知道2*3=6
你就说搜索引擎找不到答案
那我的确可以认为,百度解决不了...

[ 本帖最后由 peach5460 于 2013-8-7 09:30 编辑 ]

呵呵，你就是想给你的low++、high--讨个说法呗

那我告诉你，没戏，它跟你第一段的算法是换汤不换药，仍然是顺序遍历。只不过之前的是从内向外，而这个是从外向内。

举个精确的例子吧，比如数组有1万个元素，前4999个全是0，后5000个全是2，剩下那一个是1。你自己想想要数这数组里有几个1，你的代码会计算多少次？

也许昨天我这奖励消息发布的有点晚，很多人压根就没看到。如果大家还有兴趣的话，我可以延长一下时间。

如果没人想再试了我就发布代码（剧透，我的函数体中只有4行代码）

我服你们了，各位，本人水平太次，实在不好意思说话，辛苦哥哥们了

int element_count(int * set, int len, int e)
{
   int min=0,max=len-1,mid,count=0,k;
   while(min < max)
   {
       mid=(min+max)/2;
       if(set[mid]==x)
       {
      count = 1;
      for(k = mid ; k >= 0 && set[k]==x ; k --);
        count += (mid-k);
        for(k = mid ; k < len && set[k]==x ; k ++);
        count += (k-mid);   

      break;
       }
       else if(set[mid]>x)
           right=mid-1;
       else left=mid+1;
   }
   


  return count;
}

嗯,等着看一下
我是按照我发的伪码一五一十写的,没精简过...

[ 本帖最后由 peach5460 于 2013-8-7 09:41 编辑 ]

呵呵，兄弟你这和那个小姑娘的代码没什么区别，只能算是二分加顺序扫描的混合算法。为什么不把顺序扫描这部分也用二分法替代呢？

恕我直言，你们的二分法是不是只能搜索一个确定的元素？有没有想过用二分法搜索一个边界呢？

我知道你所谓的完全二分是什么意思...
不过是我贴完了以后,看到上一页那个小姑娘(你怎么知道是姑娘)的回复才看到...
还要上班,所以不想再写下去了...

PS:我想大致的思路就是将if(set.at(middle) == e) return
变成 set.at(middle - 1) > e && set.at(middle) == e 才return吧...

PPS:
上面说错了...
不是set.at(middle - 1) > e && set.at(middle) == e
是 l < m = r...
我再真的不想了,我要好好上班

[ 本帖最后由 peach5460 于 2013-8-7 09:51 编辑 ]

就是想。你那样做效率真的比这样好么