首页 > 汇编语言 > 汇编语言字符串和数组
阅读:167
汇编语言对半查找(二分查找)简述
数组查找是日常编程中最常见的一类操作。对小型数组 (1000 个元素或更少 ) 而言,顺序查找(sequential search) 是很容易的,从数组开始的位置顺序检查每一个元素,直到发现匹配的元素为止。对任意 n 个元素的数组,顺序查找平均需要比较 n/2 次。如果查找的是小型数组,则执行时间也很少。但是,如果查找的数组包含一百万个元素就需要相当多的处理时间了。
对半查找 (binary search) 算法用于从大型数组中查找一个数值是非常有效的。但是它有一个重要的前提:数组必须是按升序或降序排列。下面的算法假设数组元素是升序:
开始查找前,请求用户输入一个整数,将其命名为 searchVal
1) 被查找数组的范围用下标行 first 和 last 来表示。如果 first > last,则退出查找,也就是说没有找到匹配项。
2) 计算位于数组 first 和 last 下标之间的中点。
3) 将 searchVal 与数组中点进行比较:
4) 返回步骤 1
对半查找效率高的原因是它采用了分而治之的策略。每次循环迭代中,数值范围都被对半分为成两部分。通常它被描述为 O (log n) 算法,即,当数组元素增加 n 倍时,平均查找时间仅增加 log₂n 倍。
为了帮助了解对半查找效率有多高,下表列出了数组大小相同时,顺序查找和对半查找需要执行的最大比较次数。表中的数据代表的是最坏的情况一一在实际应用 中,经过更少次的比较就可能找到匹配数值。
下面是用 C++ 语言实现的对半查找功能,用于有符号整数数组:
对半查找 (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
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频