四、斐波那契查找（黄金分割法）

思路分析

即:数组长度不足时补足，然后用特殊mid值做递归
代码实现

package Search.fib2;

import java.util.Arrays;

public class FibonacciSearch2 {
    public static int maxSize = 20;//确定斐波那契数组的大小
    public static void main(String[] args) {
        int[] arr = {1, 3, 14, 22, 23, 100};
        System.out.println(fibSearch(arr, 100));
    }

    //非递归方法得到一个斐波那契数列
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0]=1;
        f[1]=1;
        for (int i = 2; i < maxSize; i++) {
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }

    //非递归方式编写算法
    public static int fibSearch(int[] a,int key){//key:我们需要查找的关键码（值）
        int low = 0;
        int high = a.length-1;
        int k = 0;//表示斐波那契分割数值点的对应下标
        int mid =0;
        int f[]=fib();
        while (a.length>f[k]-1){//说明还没有找到
            k++;
        }
        int[] temp = Arrays.copyOf(a,f[k]-1);//不足的部分会被0填充
        for (int i = a.length; i < temp.length; i++) {
            temp[i]= a[high];
        }

        //使用while循环来找到我们的数
        while (low<=high){
            mid = low+f[k-1]-1;
            if (key<temp[mid]){//应该继续向左查找
                high=mid-1;
                //为什么是k--,因为f[k]=f[k-1]+f[k-2]，分别是全部=前+后
                //k--相当于把前部分再次拆分
                k--;
            } else if (key>temp[mid]){
                low=mid+1;
                k-=2;
            } else {
                if (mid<=high){//控制超出原来数组的元素对应的下标
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;//没有找到
    }
}

第五章：哈希表




代码实现

package HashTable;

public class HashTableDemo {
    public static void main(String[] args) {
        HashTable table = new HashTable(5);
        Emp e1 = new Emp(1, "faker");
        Emp e2 = new Emp(2, "Bengie");
        Emp e3 = new Emp(3, "Bang");
        Emp e4 = new Emp(7, "Wolf");

        table.add(e1);
        table.add(e2);
        table.add(e3);
        table.add(e4);

        table.list();
        System.out.println("==============");
        System.out.println(table.find(10));
    }

}

//哈希表
class HashTable {
    private LinkedList1[] listArray;
    private int size;//共有多少条链表

    public HashTable(int size) {
        this.size = size;
        //初始化链表
        listArray = new LinkedList1[size];//不能直接用，此时只创建了链表集，没有初始化链表，会报空指针异常
        for (int i = 0; i < size; i++) {
            listArray[i] = new LinkedList1();
        }
    }

    //编写散列函数
    public int hashFun(int id) {
        return id % size;
    }

    //真正的动作行为由HashTable调用完成
    public void add(Emp emp) {
        //根据员工id，得到该员工应当添加到哪条链表
        int listNum = hashFun(emp.id);
        listArray[listNum].add(emp);
    }

    public void list(){
        for (int i = 0; i < size; i++) {
            listArray[i].list(i);
        }
    }

    public Emp find(int id){
        int i = hashFun(id);
        return listArray[i].findEmp(id);
    }
}

//雇员节点
class Emp {
    public int id;
    public String name;
    public Emp next;

    public Emp() {
    }

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

//创建链表
class LinkedList1 {
    //没有头节点，直接指向第一个雇员节点(有效)
//    Emp head = new Emp(0,"");
    private Emp head;

    //假定当添加雇员时，id是自增的（总是从小到大）
    //因此直接加到本链表的最后即可
    public void add(Emp emp) {
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个，使用辅助指针找到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                curEmp.next = emp;
                break;
            }
            curEmp = curEmp.next;//后移

        }
    }

    //遍历链表的雇员信息
    public void list(int no) {//链表编号
        if (head == null) {
            System.out.println("编号为"+no+"的链表为空");
            return;
        }
        Emp curEmp = head;
        while (curEmp != null) {
            System.out.printf(curEmp+"=>");
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    //根据id查找雇员
    public Emp findEmp(int id){
        if (head==null){
            System.out.println("链表为空，无法查询");
            return null;
        }
        Emp curEmp = head;
        while (curEmp!=null){
            if (curEmp.id==id){
                return curEmp;
            }
            curEmp=curEmp.next;
        }
        //说明遍历之后没找到
        return null;
    }
}