二分法查有相同元素的数组的边界如何写C

只看该作者 · 2011-9-22 14:23

我的数组是这样的，我想快速找到他们的边界。

1，1，1，1，1，1，2，2，2，2，2，3，3，3，3，3，3，3，3，3，4，4，4，4，4，4，4，6，6，6，6，6，6，6，7，7，7，7，7，7，8，8，8，8，8，8，。。。

我想快速统计出相同元素的个数，用了二分法，不知道有没有比它更好的方法？

比如想找3的边界

只看该作者 · 2011-11-24 22:54

1、定义个15维的数组
2、循环15次，写入15个随机数
3、将15个数排序（二分法只能用在有序数上）
4、开始做二分法查
'-----------------代码开始了------------------------
Option Explicit
Dim S(0 To 14) As Integer, i As Integer, j As Integer
Private Sub Form_Load()
Dim tmp As Integer
List1.Clear                            '清空List显示
For i = 0 To 14
S(i) = Rnd * 99                   '循环写入小于0-99的数
Next i
For i = 0 To 13                      '排序数组元素(升序)
For j = i + 1 To 14
      If S(j) < S(i) Then          '开始排序了
         tmp = S(j)
         S(j) = S(i)
         S(i) = tmp
      End If
Next j
Next i
For i = 0 To 14                      '将元素写在List里，便于查看
List1.AddItem S(i)
Next i
End Sub
Private Sub Command1_Click()
Dim bFnd As Boolean, lowi As Integer, maxi As Integer, ci As Integer, tmpi As Integer, MyFind As Integer, iFnd As Integer
MyFind = Val(InputBox("请输入要找的数", "查找"))          '输入一个要查找的数
bFnd = False                                              '是否找到的变量
lowi = 0                                                 '最低数索引
iFnd = 0                                                 '找了几次的变量
maxi = UBound(S)                                           '最高数索引
ci = UBound(S) \ 2                                        '二分索引
Do
      iFnd = iFnd + 1                                        '循环次数计1
      If S(ci) = MyFind Then                               '如果就是要找的数
         bFnd = True
         MsgBox "找了 " & iFnd & " 遍找到了 " & MyFind & "  ,它在该数组的第" & ci + 1 & "个元素中", vbInformation, "提示"
      Else
         If Abs(maxi - lowi) <= 1 Then Exit Do             '高低索引重叠，说明已经找完了(没找到)
         If S(ci) > MyFind Then                            '如果二分值大于要找的值，说明要往前找
            tmpi = lowi + (ci - lowi) \ 2                '重复二分索引
            maxi = ci                                     '将最高数索引定位于当前索引
            ci = tmpi                                     '置当前索引为二分后的值
         Else
            tmpi = ci + (maxi - ci) \ 2                   '向后查找做二分查
            lowi = ci                                     '最低数索引置当前索引
            ci = tmpi                                     '置当前索引为向后二分查找索引
         End If
      End If
Loop While (bFnd = False)                                  '没找到就再做二分查
If Not bFnd Then MsgBox "找了 " & iFnd & " 遍都没找到你要的数字 " & MyFind, vbInformation, "提示"
End Sub

只看该作者 · 2011-11-24 22:55

#include <iostream>
using namespace std;
#define MAX 1000
void fun(int a[], int len)
{
int tmp[MAX]={0};       //辅助数组
for ( int i=0; i<len; ++i )
{
      tmp[a[i]]++;
}
for ( i=0; i<len; ++i )
{
      if ( tmp[i]!=0 )
      {
         cout << i << "的个数" << tmp[i] << endl;
      }
}
}
int main()
{
int a[] = {1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,6,6,6,6,6,6,6};

fun(a, sizeof(a)/sizeof(int));
return 0;
}

参考鸽巢排序的。。。