数据结构之查找

àì夳堔傛蜴生んèń 2022-01-07 10:05 226阅读 0赞

本次主要包含内存中的查找有：顺序查找，折半查找，分块查找，二叉排序树查找，哈希表查找

1）顺序查找：是最简单的查找方式，如，a= \{45,53,12,3,37,24,90,100,61,78\};进行排序，java程序实现如下所示：

package com.three.five;
    
    public class SearchSX {
    
        public static void main(String[] args) {
             
            int [] a= {45,53,12,3,37,24,90,100,61,78};//定义数组
            int des=90;//需要查找的目标数字
            boolean flag=false;
            for(int i=0;i<a.length;i++) {
                if(des==a[i]) {
                    System.out.println("找到目标数字："+des+",在数组中的第 "+(i+1)+" 个位置");
                    flag=true;
                    break;
                } 
            }
            if(!flag) {
            System.out.println("定义的数组中没有目标数字");
            }
        }
    }

以上代码运行结果为：

![1447588-20190305115715682-255391775.png][]

是按照顺序一个一个进行比较查询，最快是第一次比较匹配，最慢是最后一个比较匹配，算法的时间复杂度是O（n）,

2.折半查找，也叫二分查找，需要时有序存放，查找起来会快很多，如给定的数组是（3，6，12，23，30，43，56，64，78，85，98），要查找的数据是30，方法参数可以随自己换。

则使用折半查找的程序如下所示:

package com.class02;
    
    /**
     * 折半查找：前提是有序的，每次都是以中间顺序为比较基数，可以提高查询效率
     * @Date: 2019/3/23 9:30
     * @Version: 1.0
     */
    public class QuickSort {
    
        static int []a={3,6,12,23,30,43,56,64,78,85,98};
    
        public static int paritation(int []a,int key){
            int low=0;
            int high=a.length-1;
            int mid;
            while(low<=high){
                mid=(low+high)/2;
                System.out.println("比较数据为；"+a[mid]);
                if(a[mid]==key)return mid;
                 else
                     if(a[mid]<key)low=mid+1;
                     else high=mid-1;
            }
            return -1;
        }
    
        public static void main(String []args){
             int tim=QuickSort.paritation(QuickSort.a,30);
             System.out.print("最终比较"+tim+" 次得出结果：");
        }
    }

运行结果为：

![1447588-20190323095248671-20395189.png][]

转载于:https://www.cnblogs.com/guopengxia0719/p/10477408.html

[1447588-20190305115715682-255391775.png]: /images/20211223/e274bdc8caa54e0a956cac23162cbfa5.png
[1447588-20190323095248671-20395189.png]: /images/20211223/efee10cac76344fcb2098c6d1b45228f.png