河南监理建设协会网站,集团官网建设公司,虚拟网站官网,asp网站介绍一、什么是查找查找(Searching)就是根据给定的某个值#xff0c;在查找表中确定一个其关键字等于给定值的数据元素(或记录)。查找表(Search Table)#xff1a;由同一类型的数据元素(或记录)构成的集合关键字(Key)#xff1a;数据元素中某个数据项的值#xff0c;又称为键值…一、什么是查找查找(Searching)就是根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素(或记录)。查找表(Search Table)由同一类型的数据元素(或记录)构成的集合关键字(Key)数据元素中某个数据项的值又称为键值。主键(Primary Key)可唯一地标识某个数据元素或记录的关键字。搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的因为该项目是否存在。 搜索的几种常见方法顺序查找、二分法查找、二叉树查找、哈希查找。二、无序表查找也就是数据不排序的线性查找遍历数据元素。算法分析最好情况是在第一个位置就找到了此为O(1)最坏情况在最后一个位置才找到此为O(n)所以平均查找次数为(n1)/2。最终时间复杂度为O(n)#最基础的遍历无序列表的查找算法#时间复杂度O(n)defsequential_search(lis, key):lengthlen(lis)for i inrange(length):if lis[i] key:returnielse:returnFalseif __name__ __main__:LIST [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]result sequential_search(LIST, 123)print(result)三、二分查找(Binary Search)二分查找又称折半查找优点是比较次数少查找速度快平均性能好其缺点是要求待查表为有序表且插入删除困难。因此折半查找方法适用于不经常变动而查找频繁的有序列表。首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。算法核心在查找表中不断取中间元素与查找值进行比较以二分之一的倍率进行表范围的缩小。1、二分查找的python代码实现defbinary_search(lis, key):low0high len(lis) - 1time0while low time 1mid int((low high) / 2)if key high mid - 1elif key lis[mid]:low mid 1else:#打印折半的次数print(times: %s %time)returnmidprint(times: %s %time)returnFalseif __name__ __main__:LIST [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]result binary_search(LIST, 1)print(result)运行结果为查找次数为: 3下表为02、二分查找的C语言代码实现//main.m//二分查找//Created by 侯垒 on 2019/7/1.//Copyright © 2019 可爱的侯老师. All rights reserved.# includeint binary_search(int array[],int key,intlen){int low 0;int high len-1;int time 0;while (low{time;int mid (int)(lowhigh)/2;if (key{high mid-1;}else if(keyarray[mid]){low mid1;}else{//打印这本的次数printf(查询次数 %d\n,time);returnmid;}}printf(查询次数 %d\n,time);return -1;}int main(int argc, const char *argv[]){int array[11] {1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444};int index binary_search(array, 1, 11);printf(下标是 %d\n,index);return 0;}运行结果为查询次数 3下标是 0四、插值查找在介绍插值查找之前首先考虑一个新问题为什么上述算法一定要是折半而不是折四分之一或者折更多呢打个比方在英文字典里面查“apple”你下意识翻开字典是翻前面的书页还是后面的书页呢如果再让你查“zoo”你又怎么查很显然这里你绝对不会是从中间开始查起而是有一定目的的往前或往后翻。同样的比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5 我们自然会考虑从数组下标较小的开始查找。经过以上分析折半查找这种查找方式不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下mid(lowhigh)/2, 即midlow1/2*(high-low);通过类比我们可以将查找的点改进为如下midlow(key-list[low])/(list[high]-list[low])*(high-low)也就是将上述的比例参数1/2改进为自适应的根据关键字在整个有序表中所处的位置让mid值的变化更靠近关键字key这样也就间接地减少了比较次数。基本思想基于二分查找算法将查找点的选择改进为自适应选择可以提高查找效率。当然差值查找也属于有序查找。注对于表长较大而关键字分布又比较均匀的查找表来说插值查找算法的平均性能比折半查找要好的多。反之数组中如果分布非常不均匀那么插值查找未必是很合适的选择。复杂度分析查找成功或者失败的时间复杂度均为O(log(n))。1、插值查找的python代码实现defchazhi_search(lis, key):low0high len(lis) - 1time0while low time 1#计算mid值是插值算法的核心代码mid low int((key - lis[low])/(lis[high] - lis[low]) * (high -low))print(mid%s, low%s, high%s %(mid, low, high))if key high mid - 1elif key lis[mid]:low mid 1else:#打印查找的次数print(查询次数: %s %time)returnmidprint(times: %s %time)returnFalseif __name__ __main__:LIST [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]index chazhi_search(LIST, 1)print(下标为%s%index)运行结果为mid0, low0, high10查询次数:1下标为02、插值查找的C语言代码实现//main.m//插值查找//Created by 侯垒 on 2019/7/1.//Copyright © 2019 可爱的侯老师. All rights reserved.#includeint chazhi_search(int array[],int key,intlen){int low 0;int high len-1;int time 0;while (low{time;//计算mid值是插值算法的核心代码int mid low (int)((key - array[low])/(array[high]-array[low])*(high-low));printf(mid%d, low%d, high%d\n,mid, low, high);if (key{high mid-1;}else if (keyarray[mid]){low mid1;}else{//打印查找的次数printf(查询次数:%d\n,time);returnmid;}}printf(查询次数:%d\n,time);return -1;}int main(int argc, const char *argv[]) {int arr[] {1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444};int index chazhi_search(arr, 1, 11);printf(下标为%d\n,index);return 0;}运行结果为mid0, low0, high10查询次数:1下标为0
