汇编语言对半查找(二分查找)简述

< 上一页冒泡排序简述 Java字符串处理下一页 >

数组查找是日常编程中最常见的一类操作。对小型数组 (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
< 上一页冒泡排序简述 Java字符串处理下一页 >