java中常用的查询算法

1、线性查找

直接从左往右遍历，有则返回

适合数组或链表

public static void main(String[] args) {int[] arr = { 12, 34, 32, 56, 78, 23, 34, 56, 67 };int num = 34;System.out.println(fangno(arr, num));}public static ArrayList fangno(int[] arr, int num) {ArrayList list = new ArrayList<>();for (int i = 0; i < arr.length; i++) {if (arr[i] == num) {list.add(i);}}return list;}

2、二分查找

元素必须是有序的，无序的话要先排序，但是排序再在查找得到的值就不是数据原来的值了，就只能判断目标数字是否在容器内。所以最好一开始就是有序的。

1.二分查找的优势?
提前查找效率
2.二分查找的前提条件?
数据必须是有序的
如果数据是乱的，先排序再用二分查找得到的索引没有实际意义，只能确定当
前数字在数组中是否存在，因为排序之后数字的位置就可能发生变化了
3.二分查找的过程
min和max表示当前要查找的范围
mid是在min和max中间的
如果要查找的元素在mid的左边，缩小范围时，min不变，max等于micX
如果要查找的元素在mid的右边，缩小范围时，max不变，min等于mid加T

	public static void main(String[] args) {int[] arr = { 12, 17, 26, 29, 31, 38, 45, 49, 53, 58, 65, 69, 76, 79, 82, 88, 91, 99 };int num = 17;System.out.println(fangno(arr, num));}public static int fangno(int[] arr, int num) {int left = 0;int right = arr.length - 1;int s = -1;while (true) {if (left > right) {return -1;}int mid = (left + right) / 2;if (arr[mid] < num) {left = mid + 1;} else if (arr[mid] > num) {right = mid - 1;} else {s = mid;return s;}}}

3、插值查找

在介绍插值查找之前，先考虑一个问题：为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？二分查找中查找点计算如下： mid=(min+max)/2, 即mid=min+1/2*(max-min); 我们可以将查找的点改进为如下： mid=min+(num-a[min])/(a[max]-a[min])*(max-min)，这样，让mid值的变化更靠近关键字num，这样也就间接地减少了比较次数。

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。 **细节：**对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。代码跟二分查找类似，只要修改一下mid的计算方式即可。

	private static int insertSearch1(int arr[],int target){/*初始化左右搜索边界*/int left=0,right=arr.length-1;int mid;while(left<=right){mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);/*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/if(target<arr[mid]){right=mid-1;/*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/}else if(target>arr[mid]){left=mid+1;/*搜索到对应元素*/}else if(target==arr[mid]){return mid;}}/*搜索不到返回-1*/return -1;}

4、斐波那契查找

和前面的二分查找，插值查找差不多，斐波那契不过是换了一种寻找mid点的方式。这种方式中顾名思义用到了斐波那契数列。

具体好像用的少，不学习先

5、二叉树查找

二叉树查找实现

1、创建二叉树
首先，要创建一个树的节点，节点中要有该节点储存的值，然后起左右子树。示例代码：

class BinaryTree{int value;BinaryTree left;BinaryTree right;public BinaryTree(int value){this.value = value;}}

接下来就要创建二叉排序树，创建二叉排序树是一个递归的过程，需要将序列中的值一个一个添加到二叉树中。方便起见，可以利用序列中第一个元素作为根节点，再持续添加节点，示例代码：

int[] array = {35,76,6,22,16,49,49,98,46,9,40};BinaryTree root = new BinaryTree(array[0]);for(int i = 1; i < array.length; i++){createBST(root, array[i]);}

具体创建树的过程，就是一个不断与根节点比较，然后添加到左侧、右侧或不添加的过程。因为在二叉排序树中，不存在重复元素，有相等元素已经在树中时，直接忽略后续相等元素。示例代码：

public static void createBST(BinaryTree root, int element){BinaryTree newNode = new BinaryTree(element);if(element > root.value){if(root.right == null)root.right = newNode;elsecreateBST(root.right, element);}else if(element < root.value){if(root.left == null)root.left = newNode;elsecreateBST(root.left, element);}else{System.out.println("该节点" + element + "已存在");return;}}

2、二叉树查找
查找元素是否在树中的过程，就是一个二分查找的过程，不过查找的对象从左右子序列转换成了左右子树而已。示例代码：

public static void searchBST(BinaryTree root, int target, BinaryTree p){if(root == null){System.out.println("查找"+target+"失败");}else if(root.value == target){System.out.println("查找"+target+"成功");}else if(root.value >= target){searchBST(root.left, target, root);}else{ searchBST(root.right, target, root);}}

完整示例代码：

//创建一个类

public class BinaryTree {int value;BinaryTree left;BinaryTree right;public BinaryTree(int value) {this.value = value;}
}

//主函数

public class test {public static void main(String[] args) {int[] array = { 35, 2, 56, 145, 654, 23, 653, 65, 236, 78 };BinaryTree root = new BinaryTree(array[0]);for (int i = 1; i < array.length; i++) {createBST(root, array[i]);}System.out.println("中序遍历结果：");midOrderPrint(root);System.out.println();searchBST(root, 2, null);searchBST(root, 100, null);}// 创建二叉树public static void createBST(BinaryTree root, int element) {BinaryTree newNode = new BinaryTree(element);if (element < root.value) {if (root.left == null) {root.left = newNode;} else {createBST(root.left, element);}} else if (element > root.value) {if (root.right == null) {root.right = newNode;} else {createBST(root.right, element);}} else {System.out.println("该节点已存在" + element);return;}}// 查找public static void searchBST(BinaryTree root, int target, BinaryTree p) {if (root == null) {System.out.println("查找 " + target + "失败");} else if (root.value == target) {System.out.println("查找" + target + "成功");} else if (root.value > target) {// 注意这里是当根的值和目标值作比较，< ,> 不能写错了searchBST(root.left, target, root);} else {searchBST(root.right, target, root);}}public static void midOrderPrint(BinaryTree rt) {if (rt != null) {midOrderPrint(rt.left);System.out.println(rt.value + "  ");midOrderPrint(rt.right);}}
}