【软考】【数据结构与算法】查找
顺序查找
将待查找的关机子为key的元素从头到尾与表中元素进行比较,如果中间存在关键字为key的元素,则返回成功,否则查找失败。
平均查找长度为(n+1)/2
时间复杂度为O(n)
二分查找
前提条件:元素必须按顺序排列,从小到大或从大到小。
比较次数最多为log2 n +1 次
时间复杂度为O(log2 n)
用一道例题来看一下二分查找的主要思想:
整个序列已经是从小到大排列了,所以可以用二分查找。
首先确定查找区间是【1,12】,定low=1,high=12,mid = (low + high)/ 2 =6.5,取整为6,mid = 6,比较待查找关键字17与6对应的18,18>17,所以将high定为5进行第二次比较
第二次的查找区间为【1,5】,mid = 3 ,比较待查找关键字17与3对应的10,10<17,所以将low定位为4进行第三次比较
第三次的查找区间为【4,5】,mid = 4.5取整 = 4,比较带查找关键字17与4对应的16,16<17,所以将low定位为5,此时low=high=5,并且5对应的元素等于关键字17,查找结束。
注意:①mid计算时,若得到小数,应对小数进行取证操作,而不是四舍五入操作。
②比较后重新划分区间应不是mid对应的区间,而是mid±1对应的区间。
散列表
按内容存储的机制,其基本思想是:已知关键字集合U,最大关键字为m,设计一个函数Hash,它以关键字为自变量,关键字的存储地址为因变量,将关键字映射到一个有限的、地址连续的区间T【0……n-1】(n<