3.顺序香找性能分析n+11 n(n+l)我pc=ASL顺序查找xi=-x22ni=l ni=1。最坏：查找不成功时，比较N次。顺序查找的优点是算法简单，对表结构无任何要求。·既适用于顺序表，也适用于链表。·顺序查找的表中元素可以是无序的。，顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法
2 1 2 1 1 ( 1) 1 1 + = + = = = = = n n n n i n ASL p c n i n i 顺序查找 i i 3.顺序查找性能分析 • 最坏：查找不成功时，比较 N 次 • 顺序查找的优点是算法简单，对表结构无任何要求。 • 既适用于顺序表，也适用于链表。 • 顺序查找的表中元素可以是无序的。 • 顺序查找的缺点是查找效率低，当 n 较大时，不宜采 用顺序查找，而必须寻求更好的查找方法
8.2.2二分查找·引入：猜价格特征：数据有序·策略：选中间点比较，缩小查找范围，二分查找，也称折半查找，是一种高效率的查找方法。但要求表中元素必须按关键字有序（升序或降序，现设表中元素为升序排列)
8.2.2二分查找 • 引入：猜价格 • 特征：数据有序 • 策略：选中间点比较，缩小查找范围 • 二分查找，也称折半查找，是一种高效率的查找方法。但要 求表中元素必须按关键字有序(升序或降序，现设表中元素 为升序排列)
例如，假设给定有序表中关键字为查找K-21025893467110219213193780[0556647488Alowhig初始情形(a)01235678941013192156647480889205371/个Ahigmidlow(b)经过一次比较后的情形
例如，假设给定有序表中关键字为 查找K=21 [ 05 13 19 21 37 56 64 74 80 88 92 ] low hig (a) 初始情形 0 1 2 3 4 5 6 7 8 9 10 [ 05 13 19 21 37 ] 56 64 74 80 88 92 low hig mid (b) 经过一次比较后的情形 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10