Masm64：查找算法

1. 线性查找算法

原理

线性查找（Linear Search）是一种简单的查找算法，它从数组的第一个元素开始，逐个比较元素与要查找的目标值，直到找到目标值或者遍历完整个数组。

代码实现

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
array DWORD 10, 20, 30, 40, 50
target DWORD 30
array_size EQU ($ array) / TYPE array
.CODE
main PROC
mov ecx, array_size
mov esi, 0
search_loop:
mov eax, array[esi]
cmp eax, target
je found
add esi, 4
loop search_loop
jmp not_found
found:
; 这里可以添加找到目标后的处理代码，如显示找到的位置等
jmp end_search
not_found:
; 这里可以添加未找到目标后的处理代码，如显示未找到信息
end_search:
mov eax, 0
ret
main ENDP
END main

2. 二分查找算法

原理

二分查找（Binary Search）要求数组是有序的。它每次比较中间元素与目标值，如果中间元素等于目标值，则查找成功；如果中间元素大于目标值，则在数组的左半部分继续查找；如果中间元素小于目标值，则在数组的右半部分继续查找。这样每次查找都能将查找范围缩小一半。

代码实现

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
array DWORD 10, 20, 30, 40, 50
target DWORD 30
array_size EQU ($ array) / TYPE array
.CODE
main PROC
mov esi, 0
mov edi, array_size 1
binary_search:
cmp esi > edi
ja not_found
mov ebx, (esi + edi) / 2
mov eax, array[ebx * 4]
cmp eax, target
je found
jl left_half
mov esi, ebx + 1
jmp binary_search
left_half:
mov edi, ebx 1
jmp binary_search
found:
; 这里可以添加找到目标后的处理代码
jmp end_search
not_found:
; 这里可以添加未找到目标后的处理代码
end_search:
mov eax, 0
ret
main ENDP
END main

3. 哈希查找算法（简单示例）

原理

哈希查找（Hash Search）通过一个哈希函数将关键字转换为数组的索引（哈希值），然后直接访问数组中的元素。理想情况下，查找时间复杂度可以达到O(1)，但可能会遇到哈希冲突（不同关键字得到相同哈希值）的情况，需要处理冲突。

代码实现（简单的余数法哈希函数示例，处理冲突采用线性探测）

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
hash_table DWORD 10 DUP(?)
keys DWORD 123, 456, 789
key_count EQU ($ keys) / TYPE keys
table_size EQU 10
.CODE
main PROC
; 初始化哈希表
mov ecx, table_size
mov esi, 0
init_loop:
mov hash_table[esi * 4], 0
add esi, 4
loop init_loop
; 插入键值到哈希表
mov ecx, key_count
mov esi, 0
insert_loop:
mov eax, keys[esi]
mov ebx, eax % table_size
hash_insert:
cmp hash_table[ebx * 4], 0
je insert
add ebx, 1
cmp ebx, table_size
jl hash_insert
insert:
mov hash_table[ebx * 4], eax
add esi, 4
loop insert_loop
; 查找特定键值
mov eax, 123
mov ebx, eax % table_size
hash_find:
cmp hash_table[ebx * 4], eax
je found
add ebx, 1
cmp ebx, table_size
jl hash_find
jmp not_found
found:
; 这里可以添加找到目标后的处理代码
jmp end_search
not_found:
; 这里可以添加未找到目标后的处理代码
end_search:
mov eax, 0
ret
main ENDP
END main