基础三⼤查找

内查找和外查找：查找也有内查找和外查找之分。若整个查找过程都在内存中进⾏，则称之为内查找(internal search)；反之，若查找过程的需要访问外存，则称之为外查找(external search)。

1、顺序查找

从表中的第⼀个（或者最后⼀个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功。

#include<iostream>#include<vector>usingnamespacestd;// 顺序查找：通用，有序、无序数组都可用intseqSearch(vector<int>&arr,intkey){// 逐个遍历比对for(inti=0;i<arr.size();i++){if(arr[i]==key){returni;// 查找成功，返回下标}}return-1;// 查找失败}intmain(){// 无序数组测试vector<int>arr={3,1,7,5,2,4,9,6};cout<<"原数组：";for(intnum:arr)cout<<num<<" ";cout<<endl;inttarget=7;intpos=seqSearch(arr,target);if(pos!=-1)cout<<"顺序查找：元素"<<target<<" 找到，下标为："<<pos<<endl;elsecout<<"顺序查找：元素"<<target<<" 未找到"<<endl;return0;}

2、折半查找

先确定待查记录所在的范围（区间），然后逐步缩小范围知道找到或者找不到该记录为止。

#include<iostream>#include<vector>usingnamespacestd;// 折半查找（二分查找）：仅适用于升序有序数组intbinSearch(vector<int>&arr,intkey){intleft=0;intright=arr.size()-1;while(left<=right){intmid=(left+right)/2;if(arr[mid]==key){returnmid;// 找到目标，返回下标}elseif(arr[mid]>key){right=mid-1;// 目标在左区间}else{left=mid+1;// 目标在右区间}}return-1;// 查找失败}intmain(){// 必须使用有序数组vector<int>arr={1,2,3,4,5,6,7,9};cout<<"有序数组：";for(intnum:arr)cout<<num<<" ";cout<<endl;inttarget=6;intpos=binSearch(arr,target);if(pos!=-1)cout<<"折半查找：元素"<<target<<" 找到，下标为："<<pos<<endl;elsecout<<"折半查找：元素"<<target<<" 未找到"<<endl;return0;}

3、分块查找

将无序的原始数据表，按规则分成若干块（块内无序、块间有序）；同时建立一张索引表，记录每块的最大值与块起始地址。查找时先查索引确定目标所在块，再到对应块内顺序查找。

#include<iostream>#include<vector>usingnamespacestd;// 索引表结构体：记录每块最大值、块起始下标structIndex{intmaxVal;intstart;};// 分块查找intblockSearch(vector<int>&arr,vector<Index>&indexTable,intkey){// 1、索引表查找：确定目标所在块intblockNum=indexTable.size();intfindBlock=-1;for(inti=0;i<blockNum;i++){if(key<=indexTable[i].maxVal){findBlock=i;break;}}if(findBlock==-1)return-1;// 2、块内顺序查找intstart=indexTable[findBlock].start;// 确定当前块结束下标intend;if(findBlock==blockNum-1)end=arr.size()-1;elseend=indexTable[findBlock+1].start-1;for(inti=start;i<=end;i++){if(arr[i]==key)returni;}return-1;}intmain(){// 数据：块间有序、块内无序// 第0块：{3,1,2} 最大值3// 第1块：{5,4,6} 最大值6// 第2块：{9,7} 最大值9vector<int>arr={3,1,2,5,4,6,9,7};// 构建索引表vector<Index>indexTable={{3,0},{6,3},{9,6}};cout<<"分块存储数组：";for(intnum:arr)cout<<num<<" ";cout<<endl;inttarget=4;intpos=blockSearch(arr,indexTable,target);if(pos!=-1)cout<<"分块查找：元素"<<target<<" 找到，下标为："<<pos<<endl;elsecout<<"分块查找：元素"<<target<<" 未找到"<<endl;return0;}