Carson带你学数据结构：图文详解 - 动态查找、静态查找、散列查找

Carson.Ho

发布于 2022-03-25 15:23:23

54000

代码可运行

文章被收录于专栏：Android知识分享

运行总次数：0

代码可运行

前言

查找是数据结构中的重要操作
今天，我将主要讲解介绍查找的相关知识，如查找算法等，希望你们会喜欢。

1. 简介

本节将介绍关于查找的相关基础概念
具体请看下图：

2. 查找需求场景

对于不同的查找需求场景，会采用不同的查找类型，最终采用的查找方式（查找算法）也有所不同
具体如下

下面，将根据不同的查找需求类型，讲解对应的查找算法

3. 静态查找

定义：仅作查找操作
面向的数据结构：静态查找表
算法：顺序查找、有序查找、线性索引查找
具体介绍如下

3.1 顺序查找

具体介绍如下

3.2 有序查找

主要算法有：二分查找、插值 & 斐波那契
本文主要介绍 = 二分查找（也称：折半查找）

定义

具体实现

public class BinarySearch {

    /**
     * 二分查找方法
     *  @param srcArray：有序数组
     * @param des：需要查找的元素
     */
    public static int binarySearch(int[] srcArray, int des){

        int low = 0; // 比较区间第1位
        int high = srcArray.length-1; // 比较区间最后1位
        int middle ; // 区间的中间位置
        
        
        while(low <= high) {

            // 1. 通过折半，求出区间的中间位置
            middle = low +  (high - low)>>1;
             // 此处需特别注意以下：
           // a. mid = （low + high) / 2：当low、high都是比较大的数时，可能造成上溢除
           // b. 采用右移的位运算代替除2，提高效率

            // 2. 比较给定值和中间值
                // 2.1 若给定值 = 中间记录，则查找成功，返回该位置
            if(des == srcArray[middle]) {
                return middle;

                // 2.2 若给定值 ＜ 中间记录，则 在中间记录的左半区 继续查找
                // 即 将比较区间的最后1位 设置为 原中间位置的前1位
            }else if(des <srcArray[middle]) {
                high = middle - 1;

                // 2.3 若给定值 ＞ 中间记录，则 在中间记录的右半区 继续查找
                // 即 将比较区间的首位 设置为原中间位置的后1位
            }else {
                low = middle + 1;
            }
        }
        // 若比较区间的第1位 ≥ 最后1位，则表示查找失败，返回-1
        return -1;
    }


    /**
     * 执行 二分查找方法
     */
    public static void main(String[] args) {

        // 定义1个有序表数组
        int[] src = new int[]{1, 4, 5, 7, 8, 13,20,28};
        // 输出结果
        System.out.println("需要查找数据的数组下标 = " + binarySearch(src,8));

    }
    
}