VB 对分法是怎样的

对分查找又称为折半查找、二分查找。的算法：将给定值与有序顺序表（即已经按关键字的大小排好序的数据序列）的中间位置元素的关键字比较，相等则查找成功，不等则根据比较结果在表的前半部分或后半部分按相同方法继续查找，直到查找成功或确定查找失败。

对分查找的优点：查找效率高(最大比较次数=log2 N)；缺点：只能用于有序顺序表。

VB实现：设：①有已经由小到大排好序的含N个数据的数据序列 D(1),D(2)……D(N)，现在要确定数据 DF 是否包含在序列中及其位置（如果包含的话）；②X为当前查找区域的首数据位置，Y为当前查找区域的尾数据位置，K为当前查找区域的中间数据位置（当前查找区域的折半位置），J为DX在序列中的位置（0表示不在序列中）

J = 0: X = 1: Y = N

Do While X <= Y: K = (X + Y) / 2

If DF = D(K) Then J = K: Exit Do Else If DF >D(K) Then X = K + 1 Else Y = K - 1

Loop

Dim d(1 To 1000) As Integer

Dim num As Integer

Private Sub Command1_Click() '生成随机数按钮

num = Val(Text1.Text)

If num <= 0 Or num >= 1000 Then

Text1.Text = "数据个数不符合"

Exit Sub

End If

Randomize '初始化随机函数

List1.Clear

For i = 1 To num

j = Round(Rnd * 1000) 'rnd函数生成一个[0，1)之间的随机数

List1.AddItem Str(i) + " " + Str(j)

d(i) = j

Next

End Sub

Private Sub Command2_Click() '冒泡排序按钮

List2.Clear

For i = 1 To num - 1 '冒泡排序 递增

For j = num To i + 1 Step -1'从低向上冒泡

If d(j) <d(j - 1) Then ' 如果下个数据小，则于上一个数据交换

temp = d(j)

d(j) = d(j - 1)

d(j - 1) = temp

End If

Next j

Next i

For i = 1 To num '在列表2中显示排序后的数据

List2.AddItem Str(i) + " " + Str(d(i))

Next i

End Sub

Private Sub Command3_Click()

Key = Val(Text2.Text)

j = 1

Do While j <= num

If d(j) = Key Then

Label5.Caption = "在数组的 " + Str(j) + " 位置中"

Exit Do

End If

j = j + 1

Loop

If j = num + 1 Then

Label5.Caption = "在数组中没有找到" + Str(Key)

End If

End Sub

Private Sub Command4_Click()

Key = Val(Text2.Text)

i = 1

j = num

Do While i <= j

M = (j + i) \ 2

If d(M) = Key Then

Label6.Caption = "在数组的 " + Str(M) + " 位置中"

Exit Sub

End If

If d(M) <Key Then

i = M + 1

Else

j = M - 1

End If

Loop

Label6.Caption = "在数组中没有找到" + Str(Key)

End Sub

对分查找，过程如下：

一，首先初始化，确定查找范围：1 -- 5

设查找的范围起始下标为S，终止下标为E，则：S = 1，E = 5。

二，重复以下循环，两个步骤

1，求中点数组下标：M = Int（（S + E）/2）

2，判断中点元素与要找的数是否相等：d[M] = Key? （这里假设数组为D，要找的数为Key）

若d[M] = Key 则找到了；

否则就没找到；需要根据判断 d[M]<Key？若是，即要找的数比现在的中点大，那么可以舍弃中点以前（包括中点）的所有元素，因为数组是升序排列的，（可以想想，如果数组降序排列就需要舍弃中点以后的元素了）。（也可以想想，用d[M]>Key？作为条件判断）。

这里d[M]<Key？若是，舍弃中点以前（包括中点）的所有元素，即：S = M + 1 ，E = E；

否若，舍弃中点以后（包括中点）的所有元素，即：S = S ，E = M - 1；

3，判断若 S >E (起始下标超过终止下标了)，结论Key是找不到了；

否则，继续执行1，进行下一次查找。

现在看你的问题：

要找10，第1次中点是3，即:10>d[3]，从而得到第2次的查找范围为，4-5

第2次中点是4，即:10=d[4]，从而得到第2次就找到的结论

---