简单查找算法

查找算法

1.线性查找

原生概念：和一条直线一样的查找算法

数学概念：查找次数和时间复杂度成一次发的线性查找算法，就是一对一一个一个找（和普通人的逻辑思维是一样的）

2.二分查找（递归，非递归）

原生概念：将数据分为两段，进行查找，可以节省大部分时间

数学概念：二分查找的关键是基准的选择，不断的二分直到找到对应数据或者是没有找到数据，一般的简单的二分法（数字查找），选择的基准是中间，通过与基准的比较大小来选择是向右边还是左边进行查找，由此可以的得出通过二分查找的的数组是需要有序数组

代码实现（暂时学习的递归的方法实现）

package Lookup;
public class Erfefachazhao {

	public static void main(String[] args) {
       int arr[]= {1,2,3,4,5,6,7,8,9,10};
       
      int a= ErFen(arr, 0, arr.length-1,10);
      
      
      if (a==-1) {
		System.out.println("没有此数据");
	}else {
		System.out.println("找到数据  下标为:"+a);
		
	}
	}

public static int ErFen(int []arr ,int left ,int right,int value) {
	
	//创建中间基
	int mid=(left+right)/2;
  
	if (left>right) {
		
		return -1;
		
	}
	//右递归
	if (value >arr[mid]) {
	return	ErFen(arr, mid+1, right, value);
		
	//左递归
	} else if (value<arr[mid]){
	return	ErFen(arr, mid-1, right, value);
		
	}else {	
		return mid;	
	}
	}
}	

3.插值查找算法（插值查找公式）

理解：插值查找算法和二分查找算法非常相似，关键在插值查找算法利用了插值公式（数学公式），利用插值公式来确定基准

4.斐波那契查找（黄金分割）

理解：利用斐波那契数列的特性进行查找，也有具体的特性，基准在黄金分割点附近