经典算法之索引查询
索引查找主要分为两种查找方式
- 基本索引查找
- 分块索引查找
本文主要介绍分块索引查找 采用的是JavaScript脚本语言解释说明
索引查询
算法概念
了解一个知识，必须先要从其含义开始。 什么是分块索引查找算法呢，分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。 首先，所以查询需要一个索引表和一个待排序数组。索引表有当前起止索引和块区域内最大的值；
算法图解
一个例子了解索引查询的大概排序步骤 索引查找就犹如书籍中根据目录查询章节一样，只不过不同的是书籍中的内容页是顺序的。索引表中的key值为该区域当中的最大值，start为区域的起始下标，end为区域的结束下标。 现假设一本书，它的目录是有序的，但是每个章节内的页码是无序的，现给出一个页码，要求返回页面所在的位置（类似于数组返回查找元素的索引）；
首先，先判断所需查找的页面key值与索引表中的key值做比较，确定出该目标key值所属的区域是属于哪里，例如key值为42，那么根据索引表查询来看，目标key值42属于第二区块。（22<42<44），具体实现方法是利用折半查询（二分法查询）来进行查找，另起始值left等于0，右边界值right等于该索引表的长度-1，之后判断目标key值与索引key值，以达到筛选区域的作用；然后声明一个变量接收该区域的最小值，通过循环判断目标key值是否等于目标值，若不等于则令最小值向后移动，也就是将最小区域值扩大。然后判断是否等于目标值，是则返回数组下标+1，否则则证明数组中目标key不存在，返回-1；
索引表
数组根据索引分块
代码实现
声明待排数组和索引表
待排数组
var arr= [9,22,12,14,35,42,44,38,48,50,58,47]索引表
var indexarr=[
[22,0,3],[44,4,7],[58,8,11]
]封装排序实现方法
var mysearch=function(arr,indexarr,key){
var left=0;
var right=indexarr.length-1;
while(left <= right){
let mid=Math.floor((right-left)/2) +left;
if(indexarr[mid][0]>=key){
right=mid-1;
}else{
left=mid+1;
}
}
var i=indexarr[right+1][1]; //最小边界值
//按照顺序扫描整个快
while(i< indexarr[right+1][2] &&arr[i] !=key){
i++
}
if(i<=indexarr[right+1][2]){
return i+1;
}else{
return -1
}
}代码解析
折半排序，筛选区间
var left=0;
var right=indexarr.length-1;
while(left <= right){
let mid=Math.floor((right-left)/2) +left;
if(indexarr[mid][0]>=key){
right=mid-1;
}else{
left=mid+1;
}
}折半查找不过多解析了，具体请看主页中经典算法之折半查找文章
区域中最小边界值
var i=indexarr[right+1][1]; //最小边界值按照顺序查找区域内的值是否与目标key值相比是否一致
while(i< indexarr[right+1][2] &&arr[i] !=key){
i++
}若不一致，则进入if判断，当i区域的值小于等于最大区域值的时候，说明查找的值是目标key值，并返回下标值+1；否则区域内i大于最大区域值，不存在，则返回-1；
if(i<=indexarr[right+1][2]){
return i+1;
}else{
return -1
}总结
索引查询类似于书籍查询，其能根据二分法折半查询能够大幅度的减少交换循环的次数，锁定查询区域。具有非常重要的意义。通过学习索引查询，往往能够让自己认识到一些现实生活中的做法以及原理，学会算法不仅仅是学习如何在代码中使用，更能将其中的思想代入到现实当中。
腾讯云开发者
