java选择算法、java查找算法汇总，

文章目录

• 线性查找
• 二分查找算法
• 非递归写法
• 递归写法
• 分块查找
• 二叉树查找

线性查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表

public static int query(int[] arrays, int target){
    for(int i = 0 ;i < arrays.length ; i ++){
        if(arrays[i] == target)return i;
    }
    return -1;//没找到
}

线性查找是性能最差的查找算法，时间复杂度： O(N)

二分查找算法

二分查找要求数组为有序数组。 时间复杂度： O（logN）。

非递归写法

public static int query(int[] arrays, int target){

        int begin = 0, end = arrays.length-1, mid = (begin + end) / 2;

        while(end >= begin){
            if(arrays[mid] == target)return mid;
            else if(arrays[mid] > target) end = mid - 1;
            else begin = mid + 1;
            mid = (begin + end) / 2;
        }

        return -1;//没找到
    }

递归写法

 public static int query(int[] arrays, int target, int begin, int end){

        if(begin > end) return -1;//没找到
        int mid = (begin + end) / 2;

        if(arrays[mid] == target) return mid;
        else if(arrays[mid] > target) return query(arrays, target, begin, mid - 1);
        else return query(arrays, target, mid + 1, end);
    }
    public static void main(String[] args){
        //一个有序数组
        int[] arrays = {1,3,5,6,7,9,12,50};
        int index = query(arrays, -9, 0, arrays.length - 1);
        System.out.println(index);
    }

分块查找

先建立一个索引表，索引表中对当前待查的元素进行了分块处理，每一块中包含了当前块中的最大元素，并且后一块中的元素全部大于之前元素，块的个数一般都是平均分割的。这样当查询某一元素的时候只需要先确定属于哪一个块，之后再到块中进行查找定位，他的效率是基于顺序查找和折半查找中间的，并且他比折半查找要更加灵活，不在局限于有顺序表的这一套路中了。

二叉树查找

二叉树查找是现将要查找的数组生成二叉排序树。具体参考博主的另一篇文章 java操作二叉树：构建二叉树；前序、中序、后续、层次遍历