欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

查找

程序员文章站 2022-07-12 09:10:36
...

查找表

同一类型的数据元素(或记录)的集合。

关键字

数据元素(或记录)中某个数据项的值,用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字(Primary key)。用以识别若干记录的关键字,是次关键字(Secondary Key)。

查找

查找(Searching)是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。
若查找到了数据元素,则查找成功;否则,查找失败。

查找分类:
1、静态查找和动态查找
静态查找:特定元素是否存在;查找特定元素的属性。
动态查找:插入数据元素;删除数据元素。

2、有序查找和无序查找

静态查找表各种表示方法:以顺序表或线性链表表示静态查找表

顺序表的顺序查找例子:

    private static int arrays [] = {12,15,3,56,234,13,76,45,23};

    public static void main(String[] args) {
        System.out.println(findInt(45));
    }

    private static int findInt(int key){
        for(int i = 1; i <= arrays.length ; i++){
            if(arrays[i] == key){
                return arrays[i] ;
            }
        }
        return 0;
    }

那么简单的数据查找可以这样做,如果是非常庞大的数据需要查找某个关键字的话,又怎么做呢?有没有一个标准去衡量查找的优劣呢?

我们需要知道如下几个定义:
1、查找操作的性能分析:时间复杂度、空间复杂度、算法的其他性能。
2、衡量查找算法好坏的依据:其关键字和给定值进行过比较的记录个数的平均值”
3、平均查找长度:为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值。

有序表的查找

折半查找、斐波那契查找、插值查找。

折半查找

    //折半查找算法
    public static int Binary_Search(int arr[], int n, int key) {
        int mid;
        int low = 1;//最低元素索引
        int high = n;//最高元素索引
        int flag = 0;//哨兵用来记录查找次数
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < arr[mid]) {
                high = mid - 1;
                flag++;
            } else if (key > arr[mid]) {
                low = mid + 1;
                flag++;
            } else
                return mid;
        }
        return 0;
    }

折半查找性能分析
折半查找查找过程也可用二叉树描述

折半查找的效率比顺序查找高,但折半查找只能适用于有序表,且限于顺序存储结构(对线性链表无法进行折半查找)。

插值查找:在折半查找的基础上改进。
在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。那么就不一定是折半了,有可能折一小部分,有可能折更多。

   public static int chazhiSearch(int arr[], int n, int key) {
        int low, high, mid;
        low = 1;//最低元素索引
        high = n;//最高元素索引
        while (low <= high) {
            //关键算法,效率提高不少
            mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
            if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return 0;
    }

可见,关键字分布比较均匀的情况下,比折半查找更快,

斐波那契查找:
斐波那契查找的平均性能比折半查找的好,但最坏的情况比它差。还有一个优点,分割时,只需进行加、减运算。

    public static int fibonacciSearch(int arr[], int n, int key) {
        //构造一个斐波拉切数列
        int F[] = new int[20];
        F[0] = 0;
        F[1] = 1;
        for (int j = 2; j < F.length; j++) {
            F[j] = F[j - 1] + F[j - 2];//递归构造斐波拉契数列
        }

        int mid;
        int i;
        int low = 1;
        int high = n;
        int k = 0;
        while (n > F[k] - 1) {
            k++;
        }
        for (i = n; i < F[k] - 1; i++) {
            arr[i] = arr[n];//必须扩展对象数组的后面几位元素,否则容易越界
        }
        while (low <= high) {
            mid = low + F[k - 1] - 1;
            if (key < arr[mid]) {
                high = mid - 1;
                k = k - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
                k = k - 2;
            } else {
                if (mid <= n) {
                    return mid;
                } else {
                    return n;
                }
            }
        }
        return 0;
    }

访问频度域?
以上的查找都是等概率的查找,那不同概率的查找是怎么样的呢? 这就要用到 静态树表的查找
带权路径长度和最短的为静态最优查找树。
索引顺序表的查找(分块查找)
哈希查找?