# 常见查找算法

**Repository Path**: javanoteany/Search

## Basic Information

- **Project Name**: 常见查找算法
- **Description**: 顺序查找

二分查找

插值查找

斐波那契查找

树表查找

分块查找

哈希查找
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 2
- **Created**: 2021-11-10
- **Last Updated**: 2024-10-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Java, 算法, 查找

## README

### 常见查找算法



### 简介

常见的查找算法


顺序查找

折半查找/二分查找

插值查找

斐波那契查找

树表查找

分块查找

哈希查找





### （一）顺序查找




按照顺序一个一个查找





```
import java.util.Scanner;
public class SequentialSearch {
    public static void main(String[] args) {
        int a[]={49,38,65,97,76,13,27,40,78,34,12,64,5,4,62,};
        System.out.println("请输入要查询的数字：");
        Scanner input=new Scanner(System.in);
        int input1=input.nextInt();
        SequentialSearch(a,input1);
    }
    public static void SequentialSearch(int[] arr,int input){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==input){
                System.out.println(input+"的位置为："+i);
                break;
            }
            if(i==arr.length-1)
                System.out.println("No Result!");
        }
    }
}
```

​




### （二）折半查找




折半查找 也称为二分查找，是一种效率较高的查找方法，查找时要求表中的节点按关键字的大小排序，并且要求线性表顺序存储。

- 首先用要查找的关键字值(key)与中间位置结点的关键字值(arr[mid])相比较；

- 若比较结果相等，则查找完成；若不相等，再根据要查找的关键字值(key)与该中结点关键值(mid)的大小来确定下一步在那个子表中进行；

- 若待查关键值大于中间结点的关键字值(key > arr[mid])),则应查找中间结点以后的字表，否则（key < arr[mid])），查找中间结点以前的字表；

- 重复步骤1~3，直到找到满足条件的结点，或者明确表中没有这样的结点。





```
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {6, 12, 33, 87, 90, 97, 108, 561};
        System.out.println(binarySearch(arr, 90));
        //递归查找
        System.out.println(binarySearch(arr, 0, arr.length - 1, 90));
    }
    /**
     * @param arr 待排序列
     * @param key 待查找值
     * @return 待查找值在待排序列中的位置
     */
    private static String binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) { //必须为 '<=' 否则无法匹配到指定的key；
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return "Successful matching [" + (mid + 1) + "]";
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return "Successful matching -1";
    }
    /**
     * 递归实现二分查找
     * @param arr 待排序列
     * @param start 待排序列开始值
     * @param end 待排序列结束值
     * @param key 待查找值
     * @return 待查找值在待排序列中的位置
     */
    private static int binarySearch(int[] arr, int start, int end, int key) {
        if (key < arr[start] || key > arr[end] || start > end) { //start > end 不能为'>='
            return -1;
        }
        int mid = (start + end) / 2;
        if (key > arr[mid]) {
            return binarySearch(arr, mid + 1, end, key);
        } else if (key < arr[mid]) {
            return binarySearch(arr, start, mid - 1, key);
        } else {
            return mid + 1;
        }
    }
}

```





### （三）插值查找




插值查找是折半查找的一种优化，在二分查找的基础上进一步的约束数据，要求数据是有序且数值分布均匀的，可以获得更加高效的“插值查找”算法。

二分查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

- mid=(low+high)/2, 即mid=low+1/2*(high-low);

通过类比，我们可以将查找的点改进为如下：

- mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。



注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。


复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。





```
public class InsertValueSearch {
    public static void main(String[] args) {
        int max = 100;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = i + 1;
        }
        int index = insertValueSearch(arr, 0, arr.length - 1, 100);
        if(index == -1){
            System.out.println("未找到");
        }else {
            System.out.println("下标为："+index);
        }
    }
​
    public static int insertValueSearch(int[] arr, int left, int right, int value) {
        if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
        int midValue = arr[left];
        if (value > arr[mid]) {
            return insertValueSearch(arr, mid + 1, right, value);
        } else if (value < arr[mid]) {
            return insertValueSearch(arr, left, mid - 1, value);
        } else {
            return mid;
        }
    }
}
​
```






### （四）斐波那契查找




斐波那契查找是针对斐波那契数列的特点而产生的一种查找方式：

在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：

- 相等，mid位置的元素即为所求

- mid大于target，low=mid+1;

- mid小于target，high=mid-1。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;

开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

- 相等，mid位置的元素即为所求

- mid大于target，low=mid+1,k-=2;

说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

- mid小于target，high=mid-1,k-=1。

说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。





```
import java.util.Arrays;
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] array = {1,8,10,89,1000,2000};
        System.out.println("index=" + (fibonacciSearch(array,89) + 1));
    }
    /**
     * @return 斐波那契数列
     */
    public static int[] fibonacciSequence(int maxSize) {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
​
    /**
     * 斐波那契查找
     * @param arrays 传入数组
     * @param value 待搜索的值
     * @return 下标
     */
    public static int fibonacciSearch(int[] arrays, int value) {
        int left = 0;
        int right = arrays.length - 1;
        int mid = 0;
        //存放斐波那契数列
        int[] fibArray = fibonacciSequence(10);
        //表示斐波那契分割数值的下标
        int fibIndex = 0;
        //获取到斐波那契分割数值的下标
        while (right > fibArray[fibIndex] - 1) {
            fibIndex++;
        }
​
        //fibArray[fibIndex]的值可能大于a的长度，因此需要构建一个新数组，不足的部分会使用0填充
        int[] temp = Arrays.copyOf(arrays, fibArray[fibIndex]);
​
        //将新填充的内容替换为最后的数
        //例：temp = {1,3,4,6,9,11,0,0} => {1,3,4,6,9,11,11,11}
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arrays[right];
        }
        //使用while来循环处理，找到value，前提是左指针在右指针前边
        while (left <= right) {
            mid = left + fibArray[fibIndex - 1] - 1;
            //当查找的值小于当前值时应该向数组的前边遍历
            if (value < temp[mid]) {
                right = mid - 1;
                //斐波那契数向前移一位
                fibIndex--;
            }
            //当查找的值小于当前值时应该向数组的后边遍历
            else if (value > temp[mid]) {
                left = mid + 1;
                fibIndex -= 2;
            } else {
                if (mid <= right) {
                    return mid;
                } else {
                    return right;
                }
            }
        }
        return -1;
    }
}
​
```

​
​




### （五）树表查找




树表查找的对象是以二叉树或树作为表的组织形式。树表在进行插入或删除操作时，可以方便地维护表的有序性，不需要移动表中的记录，从而减少因移动记录引起的额外时间开销。常见的树表有二叉树、平衡二叉树、B-树和B+树等。





```
public class BST { //构建二叉排序树
    public BSTNode root;
    public BST() {
        this.root = null;
    }
​
    public void insert(int data) {
        if (this.root == null) {
            root = new BSTNode();
            root.key = data;
        } else {
            bSTInsert(this.root, data);
        }
    }
​
    public void bSTInsert(BSTNode node, int key) {
        if (node==null || node.key==key) {
            return;
        } else if (node.key > key) {
            if (node.lchild == null) {
                BSTNode temp = new BSTNode();
                temp.key = key;
                node.lchild = temp;
            } else {
                bSTInsert(node.lchild, key);
            }
        } else {
            if (node.rchild==null) {
                BSTNode temp = new BSTNode();
                temp.key = key;
                node.rchild = temp;
            } else {
                bSTInsert(node.rchild, key);
            }
        }
    }
    public void createBFS(int[] a) { // 创建二叉排序树
        int i = 0;
        while (i<a.length) {
            this.insert(a[i]);
            i++;
        }
    }
    public void print() { //打印二叉排序树
        if (this.root == null) {
            System.out.println("树为空");
        } else {
            print(root);
        }
    }
    public void print(BSTNode node) { //中序遍历二叉树
        if (node == null) {
            return;
        } else {
            print(node.lchild);
            System.out.print(node.key + " ");
            print(node.rchild);
        }
    }
    /** 查找二叉排序树  */
    public BSTNode BSTSearch(int key) {
        if (this.root == null) {
            return null;
        } else {
            if (this.root.key == key) {
                return root;
            } else {
                return this.bSTSearch(root, key);
            }
        }
    }
    public BSTNode bSTSearch(BSTNode node, int key) {
        if (node.key == key) {
            return node;
        } else if (node.key > key) {
            if (node.lchild != null) {
                return bSTSearch(node.lchild, key);
            } else {
                return null;
            }
        } else {
            if (node.rchild!=null) {
                return bSTSearch(node.rchild,key);
            } else {
                return null;
            }
        }
    }
​
}
class BSTNode { // 二叉排序树节点类
    public int key;
    public BSTNode lchild;
    public BSTNode rchild;
    public BSTNode() {
        this.lchild = null;
        this.rchild = null;
    }
}

```




### （六）分块查找



分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。

​1.将待排序的数组(n)进行分块.

2.例如分为s块.

    ​那么每一块的结点个数为:n/s;

    ​最后一块的结点个数:<=n/s;

3.对每i块有要求

    ​第 i-1 块中结点的最大值<第 i 块中结点的最小值

    ​第 i 块中结点的最大值<第 i+1 块中结点的最小值

4.先找待查找的num所在的快,然后再该块中顺序找对应的num.




```
class Block {
    int maxNum;// 块中的最大值
    int startIndex;// 块在数组中的起始索引位置
    int endIndex;// 块在数组中的结束索引位置
​
    public Block(int startIndex, int endIndex, int maxNum) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.maxNum = maxNum;
    }
​
    @Override
    public String toString() {
        StringBuilder sBuilder = new StringBuilder();
        sBuilder.append("[").append(startIndex).append("~").append(endIndex).append("]");
        sBuilder.append(" maxNum=").append(maxNum);
        return sBuilder.toString();
    }
​
}
​
class BlockSearch{
    /**
     * 查找num所在的块,比较的是Block中的maxNum
     *
     * @param blocks
     * @param num
     * @return -1表示未找到所在块
     */
    private static int getBlockIndex(Block[] blocks, int num) {
        // 1.使用二分查找 找到num所在块的位置
        int low = 0;
        int high = blocks.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            // 2.表示找到的值等于当前块的最大值,那么直接返回当前索引即可
            if (num == blocks[mid].maxNum) {
                return mid;
            } else if (num > blocks[mid].maxNum) {
                low = mid + 1;
            } else if (num < blocks[mid].maxNum) {
                high = mid - 1;
            }
        }
        // 3.走到这里表示num与块中最大值一样的值,那么num就在 块的索引= (low+high)/2 中
        int resultIndex = (low + high + 1) / 2;
        if (resultIndex >= blocks.length) {
            resultIndex = -1;// 表示未找到
        }
        return resultIndex;
    }
    /**
     *
     * @param blocks 块的索引表:块中的可以无序的,但是块与块之间是有序的
     *               例如:blocks[0]中的最大值小于blocks[1]中的最小值,依次类推
     * @param array  待查询的数组
     * @param num    待查找的值
     * @return num 在array数组中的索引位置:-1表示未找到
     */
    public static int blocksSearch(Block[] blocks, int array[], int num) {
        // 1.先从块的索引表中找出当前值所在的块
        int blockIndex = getBlockIndex(blocks, num);// 快的索引
        // -1表示块未找到,那么对应num的在array肯定找不到
        if (blockIndex == -1) {
            return -1;
        }
        System.out.println("num:" + num + " 可能在第 " + blockIndex + " 块中:[" + blocks[blockIndex].startIndex + "~"
                + blocks[blockIndex].endIndex + "]");
        // 2.在块中使用顺序查找.
        int blockStart = blocks[blockIndex].startIndex;
        for (int start = blocks[blockIndex].startIndex, end = blocks[blockIndex].endIndex; start <= end; start++, end--) {
            if (num == array[start]) {
                return start;
            }
            if (num == array[end]) {
                return end;
            }
        }
        return -1;
    }
​
    public static void main(String[] args) {
        // 1. 待查找数组
        int array[] = new int[] { 16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66 };
        // 2.将数组进行分块
        // 第0块:0-5:[16, 5, 9, 12, 21, 18] maxNum=21
        // 第1块:6-11:[32, 23, 37, 26, 45, 34] maxNum=45
        // 第2块:12-17:[50, 48, 61, 52, 73, 66 ] maxNum=73
        Block b0 = new Block(0, 5, 21);
        Block b1 = new Block(6, 11, 45);
        Block b2 = new Block(12, 17, 73);
        Block blocks[] = new Block[] { b0, b1, b2 };
        System.out.println("第0块:" + b0.toString());
        System.out.println("第1块:" + b1.toString());
        System.out.println("第2块:" + b2.toString());
        // 3.查找的值
        int num = 52;
        System.out.println("开始查找:" + num);
        int index = BlockSearch.blocksSearch(blocks, array, num);
        System.out.println(num + "在数组中的索引位置: " + index);
​
    }
​
}

```




### （七）哈希查找




​在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和表中一个唯一的存储位置相对应,称这个对应关系f为哈希(散列)函数,根据这个思想建立的表称为哈希表。

在哈希表中,若出现key1≠key2,而f(key1)=f(key2),则这种现象称为地址冲突key1和key2对哈希函数f来说是同义词。根据设定的哈希函数f=H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“象作为记录中的存储位置，这一映射过程为构造哈希表(散列表)。

　　好的哈希函数应该使一组关键字的哈希地址均匀分布在整个哈希表中，从而减少冲突，常用的构造哈希函数的方法有：



(1)直接地址法。取关键字或关键字的某个线性函数值为哈希地址,即H(key)=key或H(key)=a*ket+b,其中,a和b为常数

(2)数字分析法。假设关键字是r进制数(如十进制数),并且哈希表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成哈希地址。选取的原则是使得到的哈希地址尽量避免冲突，即所选数位上的数字尽可能是随机的。

(3)平方取中法。取关键字平方后的中间几位为哈希地址。这是一种较常用的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此得到的哈希地址随机性更大。

(4)除留余数法。取关键字被某个不大于哈希表长m的数p除后所得的余数为哈希地址。即:H(key)= key mod p(p<=m)。这是一种最简单、最常用的方法,它不仅可以键字直接取模，也可在折叠、平方取中等运算上取模。





```
import java.util.HashMap;
import java.util.Map;
​
/* 哈希结点 */
class TheNode {
    int key;      // 链表中的键
    TheNode next; // 下一个节点
​
    //
    public String toString() {
        return "TheNode [key=" + key + "]";
    }
}
​
/* 在哈希表中查找关键字  */
public class HashTableSearch {
    public static int hashSearch( int[] data, int key ) {
        int index = -1;
​
        int prime = 0;
​
        // 寻找小于等于最接近链表长度的质数
/*    for ( int i = data.length; i > 1; i-- ) {
      if ( isPrimes( i ) ) {
        prime = i;
        break;
      }
    }*/
​
        Map mapDataIndex = new HashMap<>();
​
        // 寻找小于或等于最接近链表长度的质数，并遍历所有元素保存索引到 mapDataIndex
        for ( int i = data.length; i > 0; i-- ) {
            if ( isPrimes( i ) ) {
                if ( prime == 0 ) {
                    prime = i;
                }
            }
​
            mapDataIndex.put( data[ i - 1 ], i - 1 );
            //System.out.println( data[ i ] + " " + i );
        }
​
        System.out.println( mapDataIndex );
​
        // 创建哈希表
        TheNode[] hashTable = createHashTable( data, prime );
​
        // 查找哈希表中是否包含这个值
        int tableKey = key % prime;
        TheNode cur = hashTable[ tableKey ];
​
        while ( cur != null && cur.key != key ) {
            cur = cur.next;
        }
​
        //boolean flag = false;
​
        if ( cur == null ) {
            //flag = false;  // 没找到
​
            return -1;
        } else {
            //flag = true;   // 找到了
​
            return ( int ) mapDataIndex.get( key );
        }
    }
​
    /*  用求余、链表法构建哈希表   */
    public static TheNode[] createHashTable( int[] data, int prime ) {
        System.out.println( prime );
​
        TheNode[] hashtable = new TheNode[ prime ];
        int key;    // 哈希函数计算的单元地址
​
        for ( int i = 0; i < data.length; i++ ) {
            TheNode node = new TheNode();
            node.key = data[ i ];
​
            key = data[ i ] % prime;
​
            System.out.println( key + " " + node.key );
​
            if ( hashtable[ key ] == null ) {
                hashtable[ key ] = node;
            } else {
                TheNode current = hashtable[ key ];
​
                while ( current.next != null ) {
                    current = current.next;
                }
​
                current.next = node;
            }
        }
​
        return hashtable;
    }
​
    // 判断是否是质数
    public static boolean isPrimes( int n ) {
        for ( int i = 2; i <= Math.sqrt( n ); i++ ) {
            if ( n % i == 0 ) {
                return false;
            }
        }
        return true;
    }
​
    // 查找到就返回元素的索引索引
    public static void main( String[] args ) {
        //
        int search = 19;
​
        // 数组不需要排序
        int[] arr = { 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
        int index = hashSearch( arr, search );
​
        System.out.println( "是否查找到了这个值：" + search + "，它的索引是：" + index );
    }
​
}
​
```



### 注意

完整版前往公众号


### LICENSE


zjzhou

### about me

一个爱学习、爱分享、爱交流的程序员；

欢迎关注个人微信公众号【Java烂笔头】，一起交流、共同进步；