汇编语言对半查找（二分查找）简述

vlambda
2020-04-01

汇编语言对半查找（二分查找）简述

数组查找是日常编程中最常见的一类操作。对小型数组 (1000 个元素或更少 ) 而言，顺序查找(sequential search) 是很容易的，从数组开始的位置顺序检查每一个元素，直到发现匹配的元素为止。对任意 n 个元素的数组，顺序查找平均需要比较 n/2 次。如果查找的是小型数组，则执行时间也很少。但是，如果查找的数组包含一百万个元素就需要相当多的处理时间了。

对半查找 (binary search) 算法用于从大型数组中查找一个数值是非常有效的。但是它有一个重要的前提：数组必须是按升序或降序排列。下面的算法假设数组元素是升序：

开始查找前，请求用户输入一个整数，将其命名为 searchVal

1) 被查找数组的范围用下标行 first 和 last 来表示。如果 first > last，则退出查找，也就是说没有找到匹配项。

2) 计算位于数组 first 和 last 下标之间的中点。

3) 将 searchVal 与数组中点进行比较：

如果数值相等，将中点送入 EAX，并从过程返回。该返回值表示在数组中发现了匹配值。
否则，如果 searchVal 大于中点值，则将 first 重新设置为中点后一位元素的位置。
或者，如果 searchVal 小于中点值，则将 last 重新设置为中点前一位元素的位置。

4) 返回步骤 1

对半查找效率高的原因是它采用了分而治之的策略。每次循环迭代中，数值范围都被对半分为成两部分。通常它被描述为 O (log n) 算法，即，当数组元素增加 n 倍时，平均查找时间仅增加 log₂n 倍。

为了帮助了解对半查找效率有多高，下表列出了数组大小相同时，顺序查找和对半查找需要执行的最大比较次数。表中的数据代表的是最坏的情况一一在实际应用中，经过更少次的比较就可能找到匹配数值。

数组大小	顺序查找	对半查找
64	64	6
1 024	1 024	10
65 536	65 536	17
1 048 576	1 048 576	21
4 294 967 296	4 294 967 296	33

下面是用 C++ 语言实现的对半查找功能，用于有符号整数数组：

int BinSearch( int values[], const int searchVal, int count ){ int first = 0; int last = count - 1; while( first <= last ) { int mid = (last + first) / 2; if( values[mid] < searchVal ) first = mid + 1; else if( values[mid] > searchVal ) last = mid - 1; else return mid; // 成功 } return -1; // 未找至U}

该 C++ 代码示例的汇编语言程序清单如下所示：

;-------------------------------------------------------------; Binary Search procedureINCLUDE Irvine32.inc.codeBinarySearch PROC USES ebx edx esi edi, pArray:PTR DWORD, ; 数组指针 Count:DWORD, ; 数组大学 searchVal:DWORD ; 给定查找数值LOCAL first:DWORD, ; first 的位置 last:DWORD, ; last 的位置 mid:DWORD ; 中点; 接收: 数组指针、数组大小、给定查找数值; 返回: 若发现匹配项则EAX=该匹配元素在数组中的位置 否则 EAX = -1;------------------------------------------------------------- mov first,0 ; first = 0 mov eax,Count ; last = (count - 1) dec eax mov last,eax mov edi,searchVal ; EDI = searchVal mov ebx,pArray ; EBX 为数组指针L1: ; while first <= last mov eax,first cmp eax,last jg L5 ; 退出查找; mid = (last + first) / 2 mov eax,last add eax,first shr eax,1 mov mid,eax; EDX = values[mid] mov esi,mid shl esi,2 ; 将 mid 值乘 4 mov edx,[ebx+esi] ; EDX = values[mid]; if ( EDX < searchval(EDI) ); first = mid + 1; cmp edx,edi jge L2 mov eax,mid ; first = mid + 1 inc eax mov first,eax jmp L4; else if( EDX > searchVal(EDI) ); last = mid - 1;L2: cmp edx,edi jle L3 mov eax,mid ; last = mid - 1 dec eax mov last,eax jmp L4; else return midL3: mov eax,mid ; 发现数值 jmp L9 ; 返回 (mid)L4: jmp L1 ; 继续循环L5: mov eax,-1 ; 查找失败L9: retBinarySearch ENDPEND