- 线性查找算法 #
- 二分查找算法 #
- 插值查找法 #
- 裴波那契(黄金分割法) # X
1、线性查找法
有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】 要求: 如果找到了，就提示找到，并给出下标值。
public class LinearSearch {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
int index = getIndex(arr, 3);
if(index != -1){
System.out.println("查找到值：" + arr[index]);
}else{
System.out.println("没有找到该值");
}
}
public static int getIndex(int[] arr,int value){
for (int i = 0; i < arr.length; i++) {
if(arr[i] ==value){
return i;
}
}
return -1;
}
}
2、二分查找法
二分查找法又称对半查找法，它是通过找中数组中间下标数来与目标元素做比较，以此确认目标元素的可能存在下标区间，在通过递归函数进行多次的比较，直到找到目标元素存储的下标并返回。当遍历所有可能的区间后（负区间left下标>right下标时），还时没有找到的话，就返回-1。
注意：二分查找法只能用于查找有序列表，否则会结果可能会出错。
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1,8,9,20,34};
int index = search(arr, 0, arr.length - 1, 4);
if(index != -1){
System.out.printf("找到值：%d下标为%dn",arr[index],index);
}else{
System.out.println("没有找到值");
}
}
public static int search(int[] arr,int left,int right,int findVal){
int mid = (left+right)/2;
if(left > right){//所有元素查找完毕
return -1;
}
if(findVal > arr[mid]){//元素范围区间在arr[mid]右边区域
return search(arr,mid + 1,right,findVal);
}else if (findVal < arr[mid]){//元素范围区间在arr[mid]左边区域
return search(arr,left,mid -1,findVal);
}else{
return mid;
}
}
}
3、插值查找法
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
插值查找计算标数的公式：int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;
插值查找法同样要求必须是用于查找有序列表。对于数据量较大，关键字分布比较均匀的查找表来说，使用插值算法效率更高。关键字不均匀的，可能还没二分算法更好。
public class InsertValueSearch {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8};
int index = search(arr, 0, 7, 10);
if(index != -1){
System.out.println("查找到值：" + arr[index]);
}else{
System.out.println("没有找到该值");
}
}
public static int search(int[] arr,int left,int right,int findValue){
if(left > right || findValue > arr[arr.length-1] || findValue < arr[0]){
return -1;
}
int mid = left + (right-left)*(findValue-arr[left])/(arr[right]-arr[left]);
int midValue = arr[mid];
if(findValue < midValue){
return search(arr,left,mid-1,findValue);
}else if(findValue > midValue){
return search(arr,mid+1,right,findValue);
}else{
return mid;
}
}
}
11、哈希表
列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
上面的概述简单来说就是一个哈希表包含多个用于存储数据的散列表，我们存储数据时会根据数据的关键值key按某种算法也就是散列函数计算出数据存储在哪个散列表中。这种散列表的存储方式，可以便于我们的查找。
//代码实现
public class HashTabDemo {
public static void main(String[] args) {
HashTab hashTab = new HashTab(7);
hashTab.add(new Emp(1,"小明"));
hashTab.add(new Emp(2,"小智"));
hashTab.add(new Emp(3,"小猪"));
hashTab.add(new Emp(4,"小红"));
hashTab.add(new Emp(5,"小杨"));
hashTab.add(new Emp(6,"小莲"));
hashTab.add(new Emp(7,"小强"));
hashTab.add(new Emp(8,"小赵"));
Emp emp = hashTab.queryEmp(9);
System.out.println(emp);
}
}
class Emp{
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Emp{" +
"id=" + id +
", name='" + name + ''' +
'}';
}
}
class EmplinkedList{
private Emp head;
public void add(Emp emp){
if(head == null){
head = emp;
return;
}
Emp lastEmp = head;
while (true){//找到链表最后的元素
if(lastEmp.next == null){
break;
}
lastEmp = lastEmp.next;
}
lastEmp.next = emp;//将新的员工对象加在链表最后的员工后面
}
//遍历链表的雇员信息
public void list(){
if(head == null){
System.out.println("当前链表为空");
return;
}
System.out.println("当前链表的信息为");
Emp curEmp = head;
while (true){
System.out.printf("员工编号%d姓名%st",curEmp.id,curEmp.name);
if(curEmp.next == null){
break;
}
curEmp = curEmp.next;
}
}
public Emp queryEmp(int id){
Emp curEmp = head;
while (true){
if(id==curEmp.id){
return curEmp;
}
if(curEmp.next == null){
break;
}
curEmp = curEmp.next;
}
return null;
}
}
class HashTab{
private EmplinkedList[] emplinkedListArray;
private int size;//表示链表的数量
public HashTab(int size){
this.size = size;
emplinkedListArray = new EmplinkedList[size];
for (int i = 0; i < size; i++) {
emplinkedListArray[i] = new EmplinkedList();
}
}
public void add(Emp emp){
int emplinkedListNo = hashFun(emp.id);
//将emp添加到对应的链表中
emplinkedListArray[emplinkedListNo].add(emp);
}
//计算元素存储的位置
public int hashFun(int id){
return id%emplinkedListArray.length;
}
//遍历hash表
public void list(){
for (int i = 0; i < emplinkedListArray.length; i++) {
emplinkedListArray[i].list();
}
}
public Emp queryEmp(int id){
int emplinkedListNo = hashFun(id);
return emplinkedListArray[emplinkedListNo].queryEmp(id);
}
}
