python算法与数据结构-常用查找算法一(37)
2019-07-24 09:06:27来源:博客园 阅读 ()
一、什么是查找
- 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。
- 查找表(Search Table):由同一类型的数据元素(或记录)构成的集合
- 关键字(Key):数据元素中某个数据项的值,又称为键值。
- 主键(Primary Key):可唯一地标识某个数据元素或记录的关键字。
搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的,因为该项目是否存在。 搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找。
二、无序表查找
也就是数据不排序的线性查找,遍历数据元素。
算法分析:最好情况是在第一个位置就找到了,此为O(1);最坏情况在最后一个位置才找到,此为O(n);所以平均查找次数为(n+1)/2。最终时间复杂度为O(n)
# 最基础的遍历无序列表的查找算法 # 时间复杂度O(n) def sequential_search(lis, key): length = len(lis) for i in range(length): if lis[i] == key: return i else: return False if __name__ == '__main__': LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222] result = sequential_search(LIST, 123) print(result)
三、二分查找(Binary Search)
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
算法核心:在查找表中不断取中间元素与查找值进行比较,以二分之一的倍率进行表范围的缩小。
1、二分查找的python代码实现
def binary_search(lis, key): low = 0 high = len(lis) - 1 time = 0 while low < high: time += 1 mid = int((low + high) / 2) if key < lis[mid]: high = mid - 1 elif key > lis[mid]: low = mid + 1 else: # 打印折半的次数 print("times: %s" % time) return mid print("times: %s" % time) return False if __name__ == '__main__': LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444] result = binary_search(LIST, 1) print(result)
运行结果为:
查找次数为: 3
下表为:0
2、二分查找的C语言代码实现
// main.m // 二分查找 // Created by 侯垒 on 2019/7/1. // Copyright © 2019 可爱的侯老师. All rights reserved. # include <stdio.h> int binary_search(int array[],int key,int len) { int low = 0; int high = len-1; int time = 0; while (low<high) { time++; int mid = (int)(low+high)/2; if (key<array[mid]) { high = mid-1; } else if(key>array[mid]) { low = mid+1; } else { // 打印这本的次数 printf("查询次数 = %d\n",time); return mid; } } 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=(low+high)/2, 即mid=low+1/2*(high-low);
通过类比,我们可以将查找的点改进为如下:
mid=low+(key-list[low])/(list[high]-list[low])*(high-low),
也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。
基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。
注:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
复杂度分析:查找成功或者失败的时间复杂度均为O(log(n))。
1、插值查找的python代码实现
def chazhi_search(lis, key): low = 0 high = len(lis) - 1 time = 0 while low < high: 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 < lis[mid]: high = mid - 1 elif key > lis[mid]: low = mid + 1 else: # 打印查找的次数 print("查询次数: %s" % time) return mid print("times: %s" % time) return False if __name__ == '__main__': LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444] index = chazhi_search(LIST, 1) print("下标为:%s"%index)
运行结果为:
mid=0, low=0, high=10 查询次数: 1 下标为:0
2、插值查找的C语言代码实现
// main.m // 插值查找 // Created by 侯垒 on 2019/7/1. // Copyright © 2019 可爱的侯老师. All rights reserved. #include<stdio.h> int chazhi_search(int array[],int key,int len) { int low = 0; int high = len-1; int time = 0; while (low<high) { 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<array[mid]) { high = mid-1; } else if (key>array[mid]) { low = mid+1; } else { // 打印查找的次数 printf("查询次数:%d\n",time); return mid; } } 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; }
运行结果为:
mid=0, low=0, high=10 查询次数:1 下标为:0
原文链接:https://www.cnblogs.com/Se7eN-HOU/p/11115268.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:老男孩老师的博客地址
下一篇:用手机控制树莓派
- python3基础之“术语表(2)” 2019-08-13
- python3 之 字符串编码小结(Unicode、utf-8、gbk、gb2312等 2019-08-13
- Python3安装impala 2019-08-13
- 小白如何入门 Python 爬虫? 2019-08-13
- python_字符串方法 2019-08-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash