1.查找算法概述
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。
（1）查找定义
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
（2）查找算法分类
1）静态查找和动态查找
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。
（3）查找算法分析
平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。
2.二分查找（折半查找）
（1）二分查找说明
元素必须是有序的，如果是无序的则要先进行排序操作。
（2）基本思想
二分查找也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
（3）复杂度分析
最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
（4）二分查找C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include<stdio.h> //二分查找算法--基本思路：将排序好的数据存放到数组里（不能是链表） // 这只前中后标签，与中间元素比，若小于就将后变为原来的中 // 继续计算中，比较，循环，直至等于中，或循环结束。 int binsearch(int *sortedSeq, int seqLength, int keyData) { int low = 0, mid, high = seqLength - 1; while (low <= high) { mid = (low + high) / 2;//奇数，无论奇偶，有个值就行 if (keyData < sortedSeq[mid]) { high = mid - 1;//是mid-1，因为mid已经比较过了 } else if (keyData > sortedSeq[mid]) { low = mid + 1; } else { return mid; } } return -1; } int main() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int location; int target = 4; location = binsearch(array, 9, target); printf("目标位置：%d\n", location); return 0; } |
（5）二分查找C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <iostream> using namespace std; int bianrySearch(int a[], int nLength, int val) { int start = 0; int end = nLength - 1; int index = -1; while(start<=end) { index = (start+ end)/2; if(a[index] == val) { return index; } else if(a[index] < val) { start = index + 1; } else { end = index -1; } } return -1; } int main() { int a[] = {0,1,2,3,4,5,6,7,8,9,10}; for(int i = 0; i < 10; i++) { cout<<a[i]<<""; } int k =bianrySearch(a,sizeof(a)/sizeof(int),10); cout<<"5在的位置为："; cout<<k<<endl; return 0; } |
