算法07 五大查找之:索引查找

上一篇总结了二分查找,这一篇要总结的是索引查找。

关于索引,我们很容易地联想到数据库中的索引,建立了索引,可以大大提高数据库的查询速度。

索引查找又称为分块查找,是一种介于顺序查找和二分查找之间的一种查找方法,索引查找的基本思想是:首先查找索引表,可用二分查找或顺序查找,然后在确定的块中进行顺序查找。

在实现索引查找算法前需要弄清楚以下三个术语。

(1)主表。即要查找的序列。

(2)索引项。一般我们会将主表分成几个块,每个块建立一个索引,这个索引就叫索引项。

(3)索引表。即索引项的集合。

同时,索引项包括以下三点。

(1)index,即索引项在主表的关键字。

(2)start,即块内的第1个元素在主表中的位置。

(3)length,即块的长度。

索引查找的示意图

示意图如下:

索引查找的代码实现

代码:

IndexItem.java

public class IndexItem {
    public int index;
    public int start;
    public int length;

    public IndexItem(int index, int start, int length) {
        this.index = index;
        this.start = start;
        this.length = length;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public int getStart() {
        return start;
    }

    public void setStart(int start) {
        this.start = start;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }
}

IndexSearch.java

public class IndexSearch {
    // 主表
    static int[] mainList = new int[]{
            101, 102, 103, 104, 105, 0, 0, 0, 0, 0,
            201, 202, 203, 204, 0, 0, 0, 0, 0, 0,
            301, 302, 303, 0, 0, 0, 0, 0, 0, 0
    };

    // 索引表
    static IndexItem[] indexItemList = new IndexItem[]{
            new IndexItem(1, 0, 5),
            new IndexItem(2, 10, 4),
            new IndexItem(3, 20, 3)
    };

    /**
     * 索引查找算法
     *
     * @param key 给定值
     * @return 返回给定值在表中的位置
     */
    public static int indexSearch(int key) {
        IndexItem item = null;

        // 建立索引规则
        int index = key / 100;

        // ① 遍历索引表,找到对应的索引项
        for (int i = 0; i < indexItemList.length; i++) {
            // 找到索引项
            if (indexItemList[i].index == index) {
                item = indexItemList[i];
                break;
            }
        }

        // 索引表中不存在该索引项
        if (item == null) {
            return -1;
        }

        // ② 根据索引项,在主表中查找
        for (int i = item.start; i < item.start + item.length; i++) {
            if (mainList[i] == key) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 插入数据
     *
     * @param key 要插入的值
     * @return true表示插入成功,false表示插入失败
     */
    public static boolean insert(int key) {
        IndexItem item = null;

        // 建立索引规则
        int index = key / 100;
        int i = 0;
        // 遍历索引表,找到对应的索引项
        for (i = 0; i < indexItemList.length; i++) {
            if (indexItemList[i].index == index) {
                item = indexItemList[i];
                break;
            }
        }
        // 索引表中不存在该索引项
        if (item == null) {
            return false;
        }

        // 根据索引项将值插入到主表中
        mainList[item.start + item.length] = key;
        // 更新索引表
        indexItemList[i].length++;

        return true;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int i = 0; i < list.length; i++) {
                System.out.print(list[i] + " ");
                if ((i + 1) % 10 == 0) {
                    System.out.println("");
                }
            }
        }
        System.out.println("********展示结束********");
    }

    public static void main(String[] args) {
        System.out.println("********索引查找********");
        System.out.println("");
        System.out.println("原始数据:");
        display(mainList);
        System.out.println("");

        int value = 106;
        System.out.println("插入数据:" + value);
        // 插入成功
        if (insert(value)) {
            System.out.println("插入后的主表:");
            display(mainList);
            System.out.println("");

            System.out.println("元素" + value + "在列表中的位置为:" + indexSearch(value));
        }
    }
}

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(五)

指针与链表及其操作 //结构体定义 typedef struct _person{ char* firstname; char* lastna...

28950
来自专栏机器学习入门

LWC 56:718. Maximum Length of Repeated Subarray

LWC 56:718. Maximum Length of Repeated Subarray 传送门:718. Maximum Length of Repea...

22660
来自专栏C/C++基础

C++ Hash表模板

利用C++类模板实现任意类型的Hash表,提供的功能有: (1)指定shmkey或内存地址创建Hash表; (2)获取指定key元素; (3)遍历指...

61240
来自专栏运维技术迷

MySQL数据库(三):数据类型

安装环境: 操作系统版本:RHEL 6.5 版本:MYSQL 5.5 常见的信息种类: 数值型:一般用于体重、身高、成绩、工资 字符型:一般用于...

39250
来自专栏跟着阿笨一起玩NET

sql server 获取每一个类别中值最大的一条数据

SELECT  * FROM    (           SELECT    * ,                     ROW_NUMBER() OVE...

44810
来自专栏企鹅号快讯

谈谈 MySQL 隐式类型转换

来源:andyqian www.andyqian.com/2017/11/11/database/MySQLConvert/ 前言 今天我们继续回到MySQL系...

532110
来自专栏Java后端技术

你敢说自己了解单例模式?

  最近在学习设计模式,在看到单例模式的时候,我一开始以为直接很了解单例模式了,实现起来也很简单,但是实际上单例模式有着好几个变种,并且多线程中涉及到线程安全问...

11620
来自专栏CodingToDie

MySql Hash 索引

Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 ...

33630
来自专栏黑白安全

Mysql索引类型Btree和Hash的区别以及使用场景

遇到单表数据量大的时候很多开发者都会想到给相对的字段建立索引来提高性能(mysql索引的使用),但很少会去关注索引的类型该如何选择,在mysql中支持有两种类型...

29730
来自专栏Java呓语

第9章、语言结构

字符串是包含在单引号(')或双引号(")字符中的字节或字符序列。 以下几行例子是等同的:

9930

扫码关注云+社区

领取腾讯云代金券