学习笔记之查找

发表于 2020-08-08 更新于 2020-12-25 分类于数据结构与算法

[学习笔记] 查找

查找表(search table) 是由同一类型的数据元素（记录）构成的集合。

关键字：

主关键字（primary key），唯一标识记录
次关键字（secondary key）,标识多个记录

分类

静态查找表：只做查找操作
动态查找表：除了查找，插入不存在的，删除已存在的

有序表查找

前提： 有序表

折半查找

public class BinarySearch {

    public static int searchIteratively(int[] array, int key, int start, int end) {
        int index = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (key == array[mid]){
                index =  mid;
                break;
            }
            if (key > array[mid]) {
                start = mid + 1;
            } else if(key < array[mid]) {
                end = mid -1;
            }
        }
        return index;
    }

    public static int searchRecursively(int[] array, int key, int start, int end) {

        int mid = (start + end) / 2;

        if (array[mid] == key) {
            return  mid;
        }

        if (start > end ) {
            return  -1;
        }

        if (key > array[mid]) {
            return searchRecursively(array, key, mid + 1, end);
        } else {
           return searchRecursively(array, key, start, mid -1);
        }
    }

}

线性索引查找

稠密索引：索引项一定是按照关键码有序
分块索引: 常用于数据库表查找

有序表查找

线性索引查找

二叉查找树

平衡二叉树

多路查找树

散列表