文档介绍：Data Structures and Algorithms Chapter 9: Searching
College of Electronic and Information Engineering
Chongqing University of Science and Technology
Instructor: Xiong Qian
Spring 2013
窑囱碘惯道恕新酥饱食撑砖弦凡芝寓试蚁勘迹户羽粳矣帖柱肆廖薄挖磨台《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
Searching
One of the mon and time-consuming operations puter science.
The process is to find the location of a target among a list of objects.
拎净某否洼裕茂瓦瘦漫滁冀趁聊菱姆卷类巫毖溪伐寥尊酣镇棋资茎翻碗昆《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
Chapter 9
Objectives
pletion you will be able to:
Design and implement sequential searches
Discuss the relative merits of different sequential searches
Design and implement binary searches
Design and implement hash-list searches
Discuss the merits of different collision resolution algorithms
Searching
掂枢艇元鳃羹魏舆吭绰屋受喧笺况锡水早尉冻讹痕摹栓堆统甩晃挨译统题《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
Highlights
9-1 List searching
9-2 Search Implementations
9-3 Hashed list searching
9-4 Collision Resolution
范架经鸳况拂骏错悍朋吨慧咽豌旅曼抵粱甩踏揉虚颐滁预判曙炮这削来娶《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
9-1 list searches
In this section we study searches that work with arrays. The two basic searches for arrays are the sequential search and the binary search.
Sequential Search
Variations on Sequential Searches
Binary Search
Analyzing Search Algorithms
麓项蕊荡南合我臀借锨样技表峻喉善察歼呛京钥庄皮移纸戚来堆酉想铆浙《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
Sequential search
It can be used in any array
Small lists
Not searched often
殷龙辅鸳棱靡寨威助秉哈纂呻熄谜汝考会撒敷佬逛梯棋坞延雏买迂忌碱丘《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
4
21
36
14
62
91
8
22
7
81
77
10
A[0]
A[1]
A[11]
Target given
(14)
Location wanted
(3)
Locating data in unordered list
In the sequential search, we start searching for the target at the beginning of the list and continue until we find the target or we are sure that it is not in the list.
充缔谣骏****棋喂待弗尖抬松猩稀擎谱张叁啮忆离硒挎窜吕腹捏担便焉耗陇《数据结构与算法》Chap9 searching《数据结构与算法》Chap9 searching
essful search in unor