这里只是说一下线性的，b树，红黑树这种，放了平衡搜索树里。散列查找在哈希表和集合里。
基本概念：
查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
静态查找表：只需要进行查找操作。
动态查找表：除查找外，需要进行增删操作。
查找表的常见操作：
- 查找某个元素。
- 删除某个元素。
- 增加某个元素。
评价指标：
查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
平均查找长度（ASL）：所有查找过程中进行关键字的比较次数的平均值。
ASL=∑i=1nPiCiASL=\sum_{i=1}^nP_iC_iASL=∑i=1nPiCi
顺序查找
顺序查找（sequential search）是一种最简单的查找方法，一般用于数组。他从顺序表的一端开始依次将每个元素值同给定的值进行比较，若找到则返回该元素所在的下标；否则返回特定值，表示查找失败。时间复杂度O（n)O（n)O（n)。 对顺序查找算法的一个改进，可在表的尾端设置一个“岗哨”，即在查找之前把给定值x赋给数组a[]中下标为n的元素，这样在循环中就不必进行下标是否越界的检查，当比到下标为n的元素位置时，由于a[n]=x必然成立，则退出循环。
实现代码:
#include <iostream> using namespace std; int seq_Search(int a[],int n){ for(int i = 0;i < n;i++) if(a[i] == a[10]) return i; return -1;//不存在就返回-1 } int main() { int a[] = {1,3,5,7,8,9,0,2,5,6,0};//第11个是哨兵 cout<<seq_Search(a,10); return 0; } 复制代码
ASL成功=1+2+3..+nn=n+12ASL_{成功} = \frac{1+2+3..+n}{n} = \frac{n+1}{2}ASL成功=n1+2+3..+n=2n+1
ASL失败=n+1 ASL_{失败} = n+1ASL失败=n+1
如果表是有序，查找的次数可能会少一些，比如1 3 5 7 9 10一共6个数。查找成功的话，ASL和无序的情况是一样的，但是查找失败的话，如果数小于1，那么查完1，就确认没有这个数，如果大于1小于3，那么也是确认没有这个数。那么查找失败的可能就是1，2，3，4，5，6，6次，有这些可能性，如果有n个数，失败的ASL就是:
ASL失败=1+2+3..+n+nn+1=nn+1+n2ASL_{失败} = \frac{1+2+3..+n+n}{n+1} = \frac{n}{n+1} + \frac{n}{2}ASL失败=n+11+2+3..+n+n=n+1n+2n
通过得到这个ASL失败ASL_{失败}ASL失败的结果我们可以简单的想到一个查找效率高的方法，就是把查找频率高的放了前面，频率低的放了后面。当然这样很可能是无序的。
折半查找
折半查找，又称“二分查找”，仅适用于有序的顺序表。就是先找有序表的中间数，然后看比中间数大还是小，如果大就查中间数右边，如果小就看左边，也是一种分治的思想啦。这个可以直接找题。
#include <iostream> using namespace std; int Binary_Search(int a[],int n){ int low = 0,high = n - 1,mid; while(low <= high){ mid = (high + low) >> 1 ; if(a[mid] == a[10]) return mid; else if(a[mid] > a[10]) high = mid - 1; else low = mid + 1; } return -1; } int main() { int a[] = {1,3,5,7,8,9,0,2,5,6,3};//第11个是哨兵 cout<<Binary_Search(a,10); return 0; } 复制代码
折半查找的时间复杂度为:log2nlog_2 nlog2n,我们要注意折半查找的效率不一定比顺序查找快。
分块查找
分块查找，又称索引顺序查找，算法过程如下：
- 在索引表中确定待查记录所属的分块（可顺序，可折半），索引表中存储的是块中最大的数。组间的索引的顺序是有序的。
- 在块内顺序查找，组内的数据是无序的。
比如1 2 3 5 8 10 23 53这样的，分成四块|1 2|3 5|8 10|23 53|，块中的数一定小于后一个块的，大于前一个块的，先对块进行排序，再对块内进行排序。
把数字分成b组，每组s个，一共n个数字，b * s = n那么先排序组，组的平均查找长度为1+2..+bb=1+b2 \frac{1+2..+b}{b} = \frac{1 + b}{2}b1+2..+b=21+b,然后对组内的数字排序，每组s个，组内的平均查找长度为1+2..+ss=1+s2 \frac{1+2..+s}{s} = \frac{1+s}{2}s1+2..+s=21+s那么总的ASL 为ASL=s+12+b+12=s2+2s+n2s ASL = \frac{s+1}{2} + \frac{b+1}{2} = \frac{s^2 + 2s + n}{2s}ASL=2s+1+2b+1=2ss2+2s+n，通过求导等手段可以得到，ASL取最小值时s=ns = \sqrt{n}s=n,那么ASL最小=n+1ASL_{最小} = \sqrt{n} + 1ASL最小=n+1。
如果索引表是使用的折半查找那么组间排序的平均查找长度就是⌈log2(b+1)⌉\lceil log_{2}(b+1)\rceil⌈log2(b+1)⌉。那么ASL就是：ASL=⌈log2(b+1)⌉+s+12ASL =\lceil log_{2}(b+1)\rceil + \frac{s+1}{2}ASL=⌈log2(b+1)⌉+2s+1。
#include <iostream> #include<vector> using namespace std; struct block_index{ int start; //开始 int length; //长度 int index; //标识 block_index(int start,int length,int index){ this->start = start; this->length = length; this->index = index; } }; int Block_Search(int a[],vector<block_index> in,int target){ bool already_found = false; //组间查询 int start = 0,end = in.size(),n = -1; for(;start < end;start++) if(a[in[start].index] >= target) already_found = true,n = start; //组内查询 start = in[n].start,end = in[n].start +in[n].length; for(;start<end;start++) if(a[start] == target) return start; return n;//返回-1为未找到数，自己可以任意设置 } int main() { int a[] = {1,5,3,7,6,9,10,22,15,36,43}; vector<block_index> in;//存放不同块 block_index b1(0,3,1),b2(3,4,6),b3(7,2,7),b4(9,2,10); in.push_back(b1); in.push_back(b2); in.push_back(b3); in.push_back(b4); cout<<Block_Search(a,in,43); return 0; } 复制代码
插值查找
插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。插值查找类似于二分查找，但是mid的选择是不一样的。
mid=low+target−a[low]a[high]−a[low](high−low) mid = low + \frac{target - a[low]}{a[high] - a[low]}(high - low)mid=low+a[high]−a[low]target−a[low](high−low)
其他地方同二分查找是一样的。
#include <iostream> using namespace std; int Interpolation_Search(int a[],int n,int target){ int low = 0,large = n - 1,mid = 0; while(low <= large){ mid = low + (target - a[low])/(a[large] - a[low]) * (large - low); if(a[mid] == target) return mid; else if(a[mid] > target) large = mid - 1; else low = mid + 1; } return -1; } int main() { int a[] = {1,5,3,7,6,9,10,22,15,36,43}; cout<<Interpolation_Search(a,11,22); return 0; } 复制代码
斐波那契查找
斐波那契查找是在二分查找的基础上，按照斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n] (如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前非部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1)，比较结果也分为三种:
- 相等，则mid位置的元素即为所求。
- 大于mid则low = mid + 1,k -= 2。
- 小于mid则high = mid - 1,k -=1。
其时间复杂度依旧是 log2nlog_2 {n}log2n，并没有比二分查找好多少，但是很多情况下，其理论运行时间会短一点。
#include <iostream> using namespace std; int max_num = 500; void Fib(int *F){ F[0] = 1,F[1] = 1; for(int i = 2;i<max_num;i++) F[i] = F[i - 1] + F[i - 2]; } int Fib_Search(int *a,int n,int target){ int low = 0,high = n - 1,mid,k = 0; int F[max_num]; Fib(F); while(n > F[k] - 1) ++k; int * temp = new int [F[k] - 1]; memcpy(temp,a,n*sizeof(int)); for(int i = n;i <F[k] - 1;++i) temp[i] = a[n-1]; while(low <= high){ mid = low + F[k-1] - 1; if(target < temp[mid]) high = mid - 1,k -= 1; else if(target > temp[mid]) low = mid + 1,k -=2; else{ if(mid < n) return mid; else return n-1; } } delete [] temp; return -1; } int main() { int a[] = {1,5,3,7,6,9,10,22,15,36,43}; cout<<Fib_Search(a,11,22); return 0; } 复制代码
三分查找
概念：在二分查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为 三分查找，也就是三分法。 三分查找通常用来迅速确定最值。
二分查找所面向的搜索序列的要求是：具有单调性（不一定严格单调）；没有单调性的序列不是使用二分查找。 与二分查找不同的是，三分法所面向的搜索序列的要求是： 序列为一个凸性函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足不严格单调递增（递减），右侧序列必须满足不严格单调递减（递增）。如下图，表示一个有最大值的凸性函数：
#include <iostream> #include<math.h> using namespace std; const double eps = 0.0000001; double a[15]; int n; double cal(double x){ double ans = 0; for(int i = 0;i <= n;i++) ans += a[i]*pow(x,i); return ans; } double third_search(double low,double high){ while(fabs(high - low) >= eps){ double m = (high - low) / 3; double lm = low + m; double rm = high - m; if(cal(lm) < cal(rm)) low = lm; else high = rm; } return low; } int main() { double low,high; scanf("%d%lf%lf",&n,&low,&high); for(int i=n;i>=0;i--) scanf("%lf",&a[i]); low = third_search(low,high); printf("%.5f\n",low); return 0; } 复制代码
二分查找近似查找
也是在二分查找的基础上进行一定的改变。可以在一个有序的数组内找近似值。
class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { int left = 0,right = arr.size() - k,mid; while(left < right){ mid = (left + right) >> 1; if(x <= arr[mid]) right = mid; else if(x > arr[mid] && x < arr[mid + k]){ if(x - arr[mid] <= arr[mid + k] - x) right = mid; else left = mid + 1; } else left = mid + 1; } return vector<int>(arr.begin()+left,arr.begin()+left+k); } };
