查找算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6645字，纯文字阅读大概需要10分钟。

内容图文

查找算法简介

查找算法也叫搜索算法，常用于判断某个数是否在数列中，或者某个数在数列中的位置。影响查找时间长短的主要因素有算法、数据存储的方式及结构。

查找和排序算法一样，如果是以查找过程中被查找的表格或数据是否变动来分类，则可以分为静态查找（Static Search）和动态查找（Dynamic Search）。静态查找是指数据在查找过程中，该查找数据不回有添加、删除或更新等操作，例如符号表查找就属于一种静态查找。动态查找则是指所查找的数据，在查找过程中会经常性地添加、删除或更新。例如在网络上查找数据就是一种动态查找。

查找的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找等。

1. 顺序查找

顺序查找是最简单、最直接的查找算法。顾名思义，顺序查找就是将数列从头到尾按照顺序查找一遍，是适用于小数据量的查找方法。

此方法优点是数据在查找前不需要进行任何的处理与排序；缺点是查找速度较慢。

时间复杂度

最优时间复杂度：O(1)
最坏时间复杂度：O(n)

             1
            #
             顺序查找
             2
            def
             sequential_search(i_list, target):

             3
            for i in range(len(i_list)):
 4if i_list[i] == target:
 5return i
 6return -1
 7 8if__name__ == "__main__":
 9     li = [1, 22, 44, 55, 66]
10print(sequential_search(li, 0))  # -111print(sequential_search(li, 1))  # 012print(sequential_search(li, 66))  # 413print(sequential_search(li, 67))  # -1

2. 二分查找法

二分查找又称折半查找，实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。其优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

算法步骤：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。
否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

时间复杂度

最优时间复杂度：O(1)
最坏时间复杂度：O(logn)

图解二分查找过程：

技术分享图片

代码实现

返回值：如果查找成功返回目标的索引值；否则返回 -1。

方式一：递归实现

             1
            def
             binary_search(li, start_index, end_index, element):

             2
            if end_index >= start_index:
 3         mid_index = (start_index + end_index) // 2
 4if element == li[mid_index]:
 5return mid_index
 6elif element > li[mid_index]:
 7return binary_search(li, mid_index+1, end_index, element)
 8else:
 9return binary_search(li, start_index, mid_index-1, element)
10# 未找到该元素11return -1
121314if__name__ == "__main__":
15     li = list(range(100))
16print(binary_search(li, 0, len(li)-1, 0))  # 017print(binary_search(li, 0, len(li)-1, 99))  # 9918print(binary_search(li, 0, len(li)-1, 100))  # -1

方式二：非递归实现

             1
            #
             非递归实现
             2
            def
             binary_search(li, element):

             3     start_index = 0
 4     end_index = len(li) - 1
 5while end_index >= start_index:
 6         mid_index = (start_index + end_index) // 2
 7if element == li[mid_index]:
 8return mid_index
 9elif element > li[mid_index]:
10             start_index = mid_index + 1
11else:
12             end_index = mid_index - 1
13return -1
141516if__name__ == "__main__":
17     li = list(range(100))
18print(binary_search(li, 0))  # 019print(binary_search(li, 99))  # 9920print(binary_search(li, 100))  # -1

3. 斐波那契查找

斐波那契数列（Fibonacci）又称黄金分割数列，指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, ......。

在数学上，斐波那契被递归方法如下定义：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2）。该数列越往后，相邻的两个数的比值越趋向于黄金比例值（0.618）。斐波那契查找就是在二分法查找的基础上根据斐波那契数列进行分割的。

斐波那契查找作为二分法查找的变种，与二分法不相上下。根据数据在数列中的分布状态，二分法和斐波那契法很难说哪个更快一点（比如被查找数正好在数列靠前位置，斐波那契查找效率还不如二分法查找）。

原理

斐波那契查找与二分法查找几乎一样，只是在选取比较点（参照点）的位置有所区别。二分法选的是将数列中间的那个元素作为比较点（参照点），而斐波那契查找则选取了数列中间略为靠后的位置作为比较点，也就是黄金分割点。

既然叫做斐波那契查找，首先列出一个斐波那契数列。[1, 2, 3, 5, 8, 13, 21] 这个斐波那契数列只是提供了被查找数列中参照点的位置，基本上就是下标。

以 i_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 为例，共有 len(i_list)=10 个元素。选择一个比 len(i_list) 稍大的斐波那契数，也就是 13（因为斐波那契数列中没有10），比 13 小一号的斐波那契数是 8，那么首次选取的参照点就是 i_list[8]。如果被查找数比 i_list[8] 小，就看一下比 8 小一号的斐波那契数 5，第二次选取的参照点就是 i_list[5]。以此类推，就是把斐波那契数当做被查找数列的位置参数来使用。

代码实现

             1
            #
             斐波那契数列
             2
            def
             fibonacci(n):

             3     f_list = [1, 1]
 4while n > 1:
 5         f_list.append(f_list[-1] + f_list[-2])
 6         n -= 1
 7return f_list[-1]
 8 9## 斐波那契查找10def fibonacci_search(i_list, target):
1112     i_len = len(i_list)
13     start_index = 0
14     end_index = i_len - 1
1516     k = 1
17# 斐波那契数列中的最后一个元素要比i_list长度稍微大一点18while fibonacci(k) < i_len :
19         k += 1
2021while start_index < end_index:
22# 参照点的位置23         mid_index = start_index + fibonacci(k-1)
24if target == li[mid_index]:
25return mid_index
26elif target > li[mid_index]:
27             start_index = mid_index + 1
28             k -= 2
29else:
30             end_index = mid_index - 1
31             k -= 1
32# 当剩余相邻的两个元素比较时33if target == li[start_index]:
34return start_index
35elif target == li[end_index]:
36return end_index
37else:
38return -1
3940if__name__ == "__main__":
41     li = [4, 12, 24, 45, 56, 63, 78]
42print(fibonacci_search(li, 1))  # -143print(fibonacci_search(li, 4))  # 044print(fibonacci_search(li, 78))  # 6

4. 插值查找

在被查找数列中选取比较点（参照点）时，二分法采用的是重点，斐波那契法采用的是黄金分割点。二分查找法是最直观的，斐波那契查找法可能是最“美观”的，但都不是最科学的。那么，如何选取最科学的那个比较点（参照点）呢？通常情况下被查找数列都不是等差的，也不知道数列的差值分布状态，没法确定到底选择哪个点是“最优解”。插值算法则给出了一个在大多数情况下的理论上最科学的比较点（参照点）。

插值查找法也是二分查找法的进阶算法，虽然当数列中的元素分布得比较广的情况下插值查找的效果并不太好。

原理

以英文词典为例，如果是要找以"a"开头的单词，一般都不会从中间位置开始翻（二分查找法），也不会从黄金分割点（页数*0.618）的位置开始找（斐波那契查找法）。直接上就应该从字典的前面开始查找。但数学没有直觉，它会告诉我们 mid_index = left_index + (target - i_list[left_index]) * (right_index-left_index) // (i_list[right_index]-i_list[left_index])，不管是找哪个字母开头的单词，还是在任意数列中寻找任意数，这个点在大多数情况下就是最优的比较点。至于为什么这个点是最优的比较点，请自行查找答案。

对于等差数列，插值查找可能是最快的算法；而对于等比数列，效率远不如二分查找和斐波那契查找。

代码实现

             1
            def
             insert_search(i_list, target):

             2
             3     i_len = len(i_list)
 4     left = 0
 5     right = i_len - 1
 6 7while right - left > 1:
 8         mid = left + (target - i_list[left]) * (right-left) // (i_list[right]-i_list[left])
 9if mid == left:
10# 当i_list[right]和i_list[left]相差太大时，有可能导致mid一直都等于left，从而陷入死循环11             mid += 1
12if target < i_list[mid]:
13             right = mid
14elif target > i_list[mid]:
15             left = mid
16else:
17return mid
18if target == i_list[left]:
19return left
20elif target == i_list[right]:
21return right
22else:
23return -1

5. 分块查找

分块查找合以上几种查找方式有所不同：顺序查找的数列是可以无序的，二分法查找和斐波那契查找的数列的数列必须是有序的。分块查找介于两者之间，需要块有序，元素可以无序。

分块查找可以看成是顺序查找的进阶算法。虽然在分块时会耗费点时间，但是在后期的查找会快很多。一般情况下分块查找比顺序查找要快。

原理

分块查找首先按照一定的取值范围将数列分成数块（至少分成两块，否则就和顺序查找没区别了）。块内的元素是可以无序的，但块必须是有序的，意思是处于后面位置的块中的最小元素都要比前面位置块中的最大元素大。

首先将被查找数与块的分界数相比较（也可以与每个块中最大的元素比较），确定被查找数属于哪个块，然后再在对应块内逐个对比，也就是顺序查找了。

代码实现

             1
            #
             存储每个块的最大值以及数列中对应元素的个数
             2 index_list = [[25, 0], [50, 0], [75, 0], [100, 0]]
 3 i_list = [1, 3, 66, 12, 99, 43, 54, 78, 33, 41, 98]
 4 5# 制造分块数列 6def divide_block():
 7global index_list, i_list
 8# 分块后的list 9     sort_list = []
10for key in index_list:
11# 小于key[0]的元素单独成块12         sub_list = [i for i in i_list if i < key[0]]
13         key[1] = len(sub_list)
14         sort_list += sub_list
15# 过滤掉已经加入到sub_list的元素16         i_list = list(set(i_list)-set(sub_list))
17     i_list = sort_list
18# 返回分块情况19return index_list
2021# 找到目标值的块并在块中进行顺序查找22def block_search(i_list, target, index_list):
23print("i_list : %s" % i_list)
24print("index_list : %s" % index_list)
25# 起始索引26     left = 0    
27# 终止索引28     right = 0
29# 首先找到目标值所在的块30for index_info in index_list:
31         right += index_info[1]
32if target < index_info[0]:
33break34else:
35             left += index_info[1]
36# 在块中顺序查找37for i in range(left, right):
38if target == i_list[i]:
39return"%s is in the list, index is: %s" % (target, i)
40return"%s is not in the list" % target
414243if__name__ == "__main__":
44print(i_list)
45    divide_block()
46print(block_search(i_list, 3, index_list)) 
47print(block_search(i_list, 99, index_list))    
48print(block_search(i_list, 59, index_list))

原文：https://www.cnblogs.com/juno3550/p/14486225.html

内容总结

以上是互联网集市为您收集整理的查找算法全部内容，希望文章能够帮你解决查找算法所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1168910.html

来源：【匿名】

【上一篇】【ZZ】15道简单算法题【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【查找算法】教程文章相关的互联网学习教程文章

二分查找算法

问题：找出一个有序(字典序)字符串数组arr中值等于字符串v的元素的序号，如果有多个元素满足这个条件，则返回其中序号最大的。 int bisearch(char** arr, int b, int e, char* v) {//循环结束有两种情况：//若minIndex为偶数则minIndex==maxIndex;//否则就是minIndex==maxIndex-1;while (minIndex<maxIndex-1){midIndex = minIndex + (maxIndex - minIndex) / 2;//不使用(minIndex+maxIndex)/2是为了避免溢出if (strcmp(arr[m...

【Java】大话数据结构(11) 查找算法(2)（二叉排序树/二叉搜索树）【代码】【图】

本文根据《大话数据结构》一书，实现了Java版的二叉排序树/二叉搜索树。二叉排序树介绍在上篇博客中，顺序表的插入和删除效率还可以，但查找效率很低；而有序线性表中，可以使用折半、插值、斐波那契等查找方法来实现，但因为要保持有序，其插入和删除操作很耗费时间。二叉排序树(Binary Sort Tree)，又称为二叉搜索树，则可以在高效率的查找下，同时保持插入和删除操作也又较高的效率。下图为典型的二叉排序树。二叉查找树具有以下...

查找算法介绍【代码】【图】

一、在java中常用的四种查找方法：1、顺序（线性）查找2、二分查找、折半查找3、插值查找4、斐波那契查找二、简单实例1、顺序（线性）查找，依次查找，不要求数列的排序/*** 线性查找，按照顺序依次查找（不要求数列有序）*/publicclass SeqSearch {publicstaticvoid main(String[] args) {int[] num = {2, 4, 8, 12, 34, 1};int target = 8;int index = -1;for (int i = 0; i < num.length; i++) {if (num[i] == target) {System....

面试常见算法-排序查找算法

算法是程序员必被的一个技能，在面试中常常出现，下面总结了面试中出现的常见算法，这些算法程序员应该牢记在心中，要非常熟练。插入排序算法原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。要点：设立哨兵，作为临时存储和判断数组边界之用。public class InsertSort {private static void insertSort(int[] a) {int j;int tmp;fo...

三类基本查找算法（循环，二分，分块）

/******************************************************************** 循环查找，二分法查找，分块查找 (二叉查找树（二叉排序树），哈希表查找以后碰到时在做笔记) ********************************************************************///顺序查找 #include <stdio.h> int sequeceSearch(int* range,int length, int key) {for(int i=0; i<length; i++){if(range[i] == key)return i; //查找成功}return -1;//查找失败 } /...

字符串查找算法-KMP

/** * KMP algorithm is a famous way to find a substring from a text. To understand its‘ capacity, we should acquaint onself with the normal algorithm.*//** * simple algorithm * * workflow: * (say, @ct means for currently position of search text) * * step 1: match text from index @ct with pattern. * step 2: if success, step to next character. or, * * The most...

一、基于比较的查找算法（顺序查找、对分查找、分块查找）【代码】【图】

1、顺序查找：O(n)//1、顺序查找int SequentialSearch(int *array, int n, int key) {int i=0;while( i < n && array[i] != key){++i;}if (array[i] == key){cout<<"Find: ";cout<<i;return i;}else {cout<<"Not Find!";return -1;} }int SequentialSearchAdvanced(int *array, int n, int key) {int i=0;while(array[i] != key){++i;}if (i < n){cout<<"Find: ";cout<<i;return i;}else {cout<<"Not Find!";return -1;} }View C...

查找算法【代码】【图】

查找算法简介1. 顺序查找2. 二分查找3. 斐波那契查找4. 插值查找 5. 分块查找查找算法简介查找算法也叫搜索算法，常用于判断某个数是否在数列中，或者某个数在数列中的位置。影响查找时间长短的主要因素有算法、数据存储的方式及结构。查找和排序算法一样，如果是以查找过程中被查找的表格或数据是否变动来分类，则可以分为静态查找（Static Search）和动态查找（Dynamic Search）。静态查找是指数据在查找过程中，该查找数据不...

C言语次序查找算法及代码【代码】

次序査找是一种复杂的査找算法，其完成办法是从序列的肇端元素开端，逐一将序列中的元素与所要查找的元素停止比拟，假如序列中有元素与所要查找的元素相等，那么査找胜利，假如査找到序列的最初一个元素都不存在一个元素与所要査找的元素值相等，那么标明査找掉败。接下来经过一段代码来理解次序査找的详细运用。 #include <stdio.h> #include <stdlib.h> #include <memory.h> int ordersearch(int a[], int n, int des){ int i;...

常用查找算法Python实现【代码】

二分法查找（递归）：def binarySearch(arr, min, max, key):mid = int((max + min)/2)if key < arr[mid]:return binarySearch(arr, min, mid-1, key)elif key > arr[mid]:return binarySearch(arr, mid+1, max, key)elif key == arr[mid]:print("找到{0}了！是第{1}个数字！".format(key, mid))else:print("没找到！")lis = [11, 22, 33, 44, 55, 66, 77, 88, 99] result = binarySearch(lis, 0, 8, 66) 原文：https://www.cnblog...

七大查找算法【代码】【图】

阅读目录1. 顺序查找2. 二分查找3. 插值查找4. 斐波那契查找5. 树表查找6. 分块查找7. 哈希查找　　查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在...

二分查找算法【代码】

#include <stdio.h> int BinSearch(int Source[],int size,int key) { int low=0, high=size-1,mid; while(low<=high) { mid=(low+high)/2; if(Source[mid] == key) return mid; if(Source[mid] > key) high=mid-1; else low=mid+1; } return -1; }void main() { int num; int index; int ArraySource[10]={1,2,8,11,12,13...

二分查找算法

二分查找算法（也称为折半查找算法）效率相对较高，是一种在有序数组中查找某一特定元素的搜索算法。步骤：第一步：从数组的中间元素开始查找，如果数组中的中间元素等于要查找的元素，查找结束；第二步：如果要查找的元素大于或者小于数组的中间元素，则在数组大于或小于中间元素的那一半中查找，和步骤一同样从中间元素开始查找；第三步：如果数组为空，则代表找不到；折半查找算法每次把搜索范围缩小一半，时间复杂度为: log(n)...

常用查找算法总结【代码】【图】

1. 二分查找//递归版int binarySearch(constint arr[], int low, int high, int val) {if (low <= high){int mid = low + (high - low) / 2; // Do not use (low + high) / 2 which might encounter overflow issueif (val < arr[mid])return binarySearch(arr, low, mid-1, val);elseif (val > arr[mid])return binarySearch(arr, mid+1, high, val);elsereturn mid;}return -1; } //非递归版int binarySearch(constint arr[],...

查找算法总结（二）散列表【代码】【图】

时间复杂度上，红黑树在平均情况下插入，查找以及删除上都达到了lgN的时间复杂度。那么有没有查找效率更高的数据结构呢，答案就是本文接下来要介绍了散列表，也叫哈希表(Hash Table)什么是哈希表哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 查找算法

查找算法

内容导读

内容图文

查找算法简介

1. 顺序查找

时间复杂度

2. 二分查找法

算法步骤：

时间复杂度

图解二分查找过程：

代码实现

3. 斐波那契查找

原理

代码实现

4. 插值查找

原理

代码实现

5. 分块查找

原理

代码实现

内容总结

内容备注

内容手机端

【查找算法】教程文章相关的互联网学习教程文章

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程