Java 查找算法

小灰灰 2022-08-02 04:42 90阅读 0赞

这个问题有几个点要先确认

*  必须是有序，如果无序的话就只能全遍历了
 *  查找算法跟数据结构相关，不同的数据结构适用于不同的查找算法
 *  查找算法与磁盘I/O有一定的关系，比如数据库在索引排序的时候，如果每次都从磁盘读取一个节点然后进行判断

### 数组 ###

如果知道下标的话就方便了，查找的复杂度为1.  
如果是针对值的查找，那么顺序遍历是O(n),

#### 二分查找 ####

使用二分查找的话可以减少时间复杂度为：O（logn）

/** * 二分查找又称折半查找，它是一种效率较高的查找方法。 　　【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 * @author wzj * */
    public class BinarySearch {  
        public static void main(String[] args) {
            int[] src = new int[] {
       1, 3, 5, 7, 8, 9}; 
            System.out.println(binarySearch(src, 3));
            System.out.println(binarySearch(src,3,0,src.length-1));
        }
    
        /** * * 二分查找算法 * * * * @param srcArray * 有序数组 * * @param des * 查找元素 * * @return des的数组下标，没找到返回-1 */ 
       public static int binarySearch(int[] srcArray, int des){ 
    
            int low = 0; 
            int high = srcArray.length-1; 
            while(low <= high) { 
                int middle = (low + high)/2; 
                if(des == srcArray[middle]) { 
                    return middle; 
                }else if(des <srcArray[middle]) { 
                    high = middle - 1; 
                }else { 
                    low = middle + 1; 
                }
            }
            return -1;
       }
    
          /** *二分查找特定整数在整型数组中的位置(递归) *@paramdataset *@paramdata *@parambeginIndex *@paramendIndex *@returnindex */
        public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){  
           int midIndex = (beginIndex+endIndex)/2;  
           if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){
               return -1;  
           }
           if(data <dataset[midIndex]){  
               return binarySearch(dataset,data,beginIndex,midIndex-1);  
           }else if(data>dataset[midIndex]){  
               return binarySearch(dataset,data,midIndex+1,endIndex);  
           }else {  
               return midIndex;  
           }  
       } 
    }

但是插入因为会涉及当前节点后的所有值得移动，一次，其时间复杂度为O(n) + O(log n)

### 链表 ###

只能从头节点遍历， 查找的复杂度是O（n）  
插入或者是删除，因为只需要移动指针，时间复杂度为O（1） + O（n）

### 树 ###

树的查找，主要是先序遍历，中序等遍历方式。  
插入和删除，还是比较快  
常用的会有如下的衍生方式：

#### 二叉树 ####

二叉树的构建：

class BinaryNode{
            int value;
            BinaryNode left;
            BinaryNode right;
            public BinaryNode(int value){
                this.value = value;
                this.left = null;
                this.right = null;
            }
    
            public void add(int value){
                if(value > this.value){
                    if(this.right != null){
                        this.right.add(value);
                    }else{
                        this.right = new BinaryNode(value);
                    }
                }else{
                    if(this.left != null){
                        this.left.add(value);
                    }else{
                        this.left = new BinaryNode(value);
                    }
                }
            }
    
            // 中序查找
            public BinaryNode get(int value){
                if(this.value == value){
                    return this;
                }
                if(this.value > value){
                    return this.left.get(value);
                }
    
                if(this.value < value){
                    return this.right.get(value);
                }
                return null;
            }
        }

插入的复杂度本身并不高，只是简单的节点添加。但是因为寻找插入位置的查找操作的复杂度跟树的高度相关为logn，极差的情况下可能接近于线性查找。

#### 平衡二叉树 ####

平衡二叉树是尽量减少数高的二叉树，其算法中增加了左旋和右旋的操作。插入复杂度会高一些，但是会得到不错的查找性能。

#### B+Tree ####

[学习自这里][Link 1]  
这个就要说一下上面说的跟磁盘I/O相关的，因此为了减少磁盘I/O。可以利用磁盘的预读特性，一次提取大概相当于一页大小的节点到内存中。  
先要说一下B-Tree.  
一个平衡的m-way查找数，其要满足如下的条件：

*  每节点中的数据量 < m
 *  每层节点数 <= m
 *  子数节点要完全大于、小于、或者在其之间。 也就是不能越过父节点的两个值
 *  叶子节点中的值的个数>=m/2
 *  非叶子节点中的值的个数=子节点个数-1  
    如下图：  
    ![这里写图片描述][20150708191657325]  
    可以看出，三个子节点的有两个值，三个子节点中的数据分别对应了小于、之间、大于这个范围

B+Tree  
与上面的差别是：

*  所有关键字都在叶子节点
 *  父节点存储的都是到子节点的指针
 *  会有两个入口，一个是根节点，另外一个是从最小叶子节点开始的指针  
    ![这里写图片描述][20150708193549179]

查找跟二叉树比较像，因为插入的时候已经是相当于二分算法了，所以只需要，递归找到就可以了。

### Hash表 ###

为了解决一些不容易排序，或者查找的对象。 比如图像，视频等等。  
在Java的HashMap中有使用。  
是一个链表的数组  
\- 对key进行进行散列函数，求Hash值，找到其对应的链表。  
\- 剩下的解决hash冲突的问题  
\- 解决hash冲突，可以在命中链表之后顺序比较  
\- 这里顺便再说一下一致性hash. 预置很多节点，选择最近的节点存入，可以解决增加节点数据转移的问题。

[Link 1]: http://www.cnblogs.com/coder2012/p/3330311.html
[20150708191657325]: /images/20220731/24dd6a2994b34968a87118194f892ba8.png
[20150708193549179]: /images/20220731/a47e627012ce4bd9bf6aac1c53eb87ff.png