汇编语言二分查找排序代码分析(13)

 

来自于《Intel汇编语言程序设计》（第四版）第九章。

 

我们知道二分查找排序是每次比较之后都会将查找范围减半的算法，其算法时间复杂度是O(logN)，查找40亿的数据时，其时间也不过30秒左右，非常高效，不过其需要的前提是一个已经按升序或降序排序完成的数据集合。

 

下面看一下原书中用C++实现的适用于有符号整数的二分查找函数：

 

int BinSearch( int values[] , const int searchVal , int count )

{

      int first = 0 ;

      int last = count -1 ;

      while ( first <= last )

      {

            int mid = ( first + last ) / 2

            if ( values[mid] < searchVal )

                 first = mid + 1;

            else if (values[mid] > searchVal)

                 last = mid - 1;

            else

                 return mid;           ; success

      }

      return -1;                        ; not found

}

 

 

原书用汇编语言实现的部分：

 

 

;--------------------------------------------------------------------------------------

BinarySearch PROC uses ebx edx esi edi,

                      pArray:PTR DWORD,             ;pointer to array

                      Count:DWORD,                     ; array size

                      searchVal:DWORD                ; search value

LOCAL first : DWORD,                                 ; frist position

           last : DWORD,                                  ; last position

           mid : DWORD                                   ; midpoint

;

; search an array of signed integers for a single value.

; Receives : Pointer to array , array size , search value.

; Returns : If a match is found ,EAX=the array position of  the

; matching element ; otherwise , EAX=1.

;--------------------------------------------------------------------------------------

         

            mov first , 0                        ; first = 0

            mov eax,Count                   ; last = ( Count - 1 )

            dec eax

            mov last,eax

            mov edi,searchVal              ; EDI = search Val

            mov ebx,pArray                  ; EBX points to the array

 

L1:      ; while first<=last

           mov eax,first

           cmp eax,last

           jg L5                                    ; exit search

           ; 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                                ; scale mid value by 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                             ; optional

          jle L3

          mov eax,mid                            ; last = mid- 1

          dec eax

          mov last,eax

          jmp L4

         

; else return mid

L3:     mov eax,mid                           ; value found

          jmp L9                                     ; return mid

L4:     jmp L1                                     ; continue the loop

L5:     mov eax,-1                              ; search failed

L9:     ret

BinarySearch ENDP

 

          

 因为以上程序里有几个条件跳转指令，所以先复习一下这些指令格式：

 

jg,jge和jle均基于有符号数指令比较。

 

jg 目的操作数 源操作数

 

如果目的操作数大于源操作数则跳转。

 

 

jge 目的操作数 源操作数

 

如果目的操作数大于或等于源操作数则跳转。

 

 

jle 目的操作数 源操作数

 

如果目的操作数小于或等于源操作数则跳转。

 

 

 

另外还有两个移位指令shl和shr，作用如下：

 

SHL(shift left)指令对目的操作数执行逻辑左移操作。低位以0填充，移出的最高位被送到进位标志(CF)中，原来的进位标志就丢失了。

 

SHL指令格式为：

 

SHL 目的操作数 源操作数

 

而SHR完全与SHL相反，SHR(shift right)指令对目的操作数执行逻辑右移操作。移出的数据以0代替，最低位被送到进位标志(CF)中，原来的进位标志就丢失了。

 

SHL指令格式为：

 

SHL 目的操作数 源操作数

 

下面我们来看一下汇编代码。虽然程序很长，但是并不是很复杂，我们就以注释来代替讲解：

 

 

;--------------------------------------------------------------------------------------

BinarySearch PROC uses ebx edx esi edi,    ; 将寄存器的值先保存

                      pArray:PTR DWORD,               ;pArray为指DWORD类型的数组的指针

                      Count:DWORD,                       ; 数组的长度

                      searchVal:DWORD                  ; 需要查找的值

LOCAL first : DWORD,                                 ; 开始地址

           last : DWORD,                                  ; 结束地址

           mid : DWORD                                   ; 中间地址

;

; search an array of signed integers for a single value.

; Receives : Pointer to array , array size , search value.

; Returns : If a match is found ,EAX=the array position of  the

; matching element ; otherwise , EAX=1.

;--------------------------------------------------------------------------------------

         

            mov first , 0                        ; first = 0

            mov eax,Count                   ; last = ( Count - 1 )

            dec eax

            mov last,eax

            mov edi,searchVal              ; EDI = search Val

            mov ebx,pArray                  ; EBX points to the array

 

L1:      ; while first<=last

           mov eax,first

           cmp eax,last

           jg L5                                    ; 如果first大于last，则退出

           ; mid = ( last + first ) / 2

           mov eax,last

           add eax, first

           shr eax,1                              ; 通过右移位除以2

           mov mid,eax

           ; EDX=values[mid]

           mov esi,mid

           shl esi,2                                ; 因为我们现在操作的是DWORD，所以乘以4

           mov edx,[ebx+esi]                ; 这样得到的就是中间地址，把中间地址的值赋给edx

; if ( EDX < searchval[EDI])

; first = mid + 1

           cmp edx,edi                          ; 如果中间值小于要查找的数

           jge L2                                   ; 如果edx大于等于edi则跳转，否则向下执行

           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                                       ; 如果edx小于等于edi则跳转，否则向下执行

          mov eax,mid                            ; last = mid- 1

          dec eax

          mov last,eax

          jmp L4

         

; else return mid

L3:     mov eax,mid                           ; value found

          jmp L9                                     ; return mid

L4:     jmp L1                                     ; continue the loop

L5:     mov eax,-1                              ; 没有找到，返回-1

L9:     ret

BinarySearch ENDP

 

 

此汇编代码完全是按照上面C++代码的逻辑编写。