基础三⼤查找

内查找和外查找查找也有内查找和外查找之分。若整个查找过程都在内存中进⾏则称之为内查找(internal search)反之若查找过程的需要访问外存则称之为外查找(external search)。1、顺序查找从表中的第⼀个或者最后⼀个记录开始逐个进行记录的关键字和给定值的比较若某个记录的关键字和给定值比较相等则查找成功。#includeiostream#includevectorusingnamespacestd;// 顺序查找通用有序、无序数组都可用intseqSearch(vectorintarr,intkey){// 逐个遍历比对for(inti0;iarr.size();i){if(arr[i]key){returni;// 查找成功返回下标}}return-1;// 查找失败}intmain(){// 无序数组测试vectorintarr{3,1,7,5,2,4,9,6};cout原数组;for(intnum:arr)coutnum ;coutendl;inttarget7;intposseqSearch(arr,target);if(pos!-1)cout顺序查找元素target 找到下标为posendl;elsecout顺序查找元素target 未找到endl;return0;}2、折半查找先确定待查记录所在的范围区间然后逐步缩小范围知道找到或者找不到该记录为止。#includeiostream#includevectorusingnamespacestd;// 折半查找二分查找仅适用于升序有序数组intbinSearch(vectorintarr,intkey){intleft0;intrightarr.size()-1;while(leftright){intmid(leftright)/2;if(arr[mid]key){returnmid;// 找到目标返回下标}elseif(arr[mid]key){rightmid-1;// 目标在左区间}else{leftmid1;// 目标在右区间}}return-1;// 查找失败}intmain(){// 必须使用有序数组vectorintarr{1,2,3,4,5,6,7,9};cout有序数组;for(intnum:arr)coutnum ;coutendl;inttarget6;intposbinSearch(arr,target);if(pos!-1)cout折半查找元素target 找到下标为posendl;elsecout折半查找元素target 未找到endl;return0;}3、分块查找将无序的原始数据表按规则分成若干块块内无序、块间有序同时建立一张索引表记录每块的最大值与块起始地址。查找时先查索引确定目标所在块再到对应块内顺序查找。#includeiostream#includevectorusingnamespacestd;// 索引表结构体记录每块最大值、块起始下标structIndex{intmaxVal;intstart;};// 分块查找intblockSearch(vectorintarr,vectorIndexindexTable,intkey){// 1、索引表查找确定目标所在块intblockNumindexTable.size();intfindBlock-1;for(inti0;iblockNum;i){if(keyindexTable[i].maxVal){findBlocki;break;}}if(findBlock-1)return-1;// 2、块内顺序查找intstartindexTable[findBlock].start;// 确定当前块结束下标intend;if(findBlockblockNum-1)endarr.size()-1;elseendindexTable[findBlock1].start-1;for(intistart;iend;i){if(arr[i]key)returni;}return-1;}intmain(){// 数据块间有序、块内无序// 第0块{3,1,2} 最大值3// 第1块{5,4,6} 最大值6// 第2块{9,7} 最大值9vectorintarr{3,1,2,5,4,6,9,7};// 构建索引表vectorIndexindexTable{{3,0},{6,3},{9,6}};cout分块存储数组;for(intnum:arr)coutnum ;coutendl;inttarget4;intposblockSearch(arr,indexTable,target);if(pos!-1)cout分块查找元素target 找到下标为posendl;elsecout分块查找元素target 未找到endl;return0;}