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

数组查找是日常编程中最常见的一类操作。对小型数组 (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 procedure
INCLUDE Irvine32.inc
.code
BinarySearch 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 mid
L3:    mov     eax,mid                  ; 发现数值
    jmp     L9                          ; 返回 (mid)

L4:    jmp     L1                       ; 继续循环

L5:    mov     eax,-1                   ; 查找失败
L9:    ret
BinarySearch ENDP
END