四、斐波那契查找(黄金分割法)
思路分析 即:数组长度不足时补足,然后用特殊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){
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);
for (int i = a.length; i < temp.length; i++) {
temp[i]= a[high];
}
while (low<=high){
mid = low+f[k-1]-1;
if (key<temp[mid]){
high=mid-1;
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;
}
public void add(Emp emp) {
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 {
private Emp head;
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();
}
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;
}
}
|