三大查找算法(Java实现)
2020-01-27 16:01:20来源:博客园 阅读 ()
三大查找算法(Java实现)
三大查找算法
1.二分查找(Binary Search)
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {-4, -1, 0, 1, 2, 4, 5, 6, 7, 10};
System.out.println(binarySearch1(arr, 1, 0, arr.length - 1));
System.out.println(binarySearch2(arr, 1, 0, arr.length - 1));
int[] arr2 = {-4, -1, 0, 1, 2, 4, 4, 5, 6, 7, 10};
System.out.println(binarySearch3(arr2, 4, 0, arr.length - 1));
}
//非递归写法
public static int binarySearch1(int[] arr, int key, int left, int right) {
int mid;
while (left <= right) {
mid = (left + right) >> 1;
if (key < arr[mid]) {
right = mid - 1;
} else if (key > arr[mid]) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
//递归写法
public static int binarySearch2(int[] arr, int key, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) >> 1;
if (key < arr[mid]) {
return binarySearch1(arr, key, left, mid - 1);
} else if (key > arr[mid]) {
return binarySearch1(arr, key, mid + 1, right);
} else {
return mid;
}
}
//可查找重复值
public static ArrayList<Integer> binarySearch3(int[] arr, int key, int left, int right) {
if (left > right) {
return new ArrayList<>();
}
int mid = (left + right) >> 1;
if (key < arr[mid]) {
return binarySearch3(arr, key, left, mid - 1);
} else if (key > arr[mid]) {
return binarySearch3(arr, key, mid + 1, right);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(mid);
int index = mid - 1;
//向左搜索
while (true) {
if (index < 0 || arr[index] != arr[mid]) {
break;
}
list.add(index);
index--;
}
index = mid + 1;
//向右搜索
while (true) {
if (index > arr.length - 1 || arr[index] != arr[mid]) {
break;
}
list.add(index);
index++;
}
return list;
}
}
}
2.插值查找(InsertValue Search)
public class InsertValueSearch {
public static void main(String[] args) {
int[] arr = {-4, -1, 0, 1, 2, 4, 5, 6, 7, 10};
System.out.println(insertValueSearch(arr, 1, 0, arr.length - 1));
}
public static int insertValueSearch(int[] arr, int key, int low, int high) {
if (low > high) {
return -1;
}
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
if (key < arr[mid]) {
return insertValueSearch(arr, key, low, mid - 1);
} else if (key > arr[mid]) {
return insertValueSearch(arr, key, mid + 1, high);
} else {
return mid;
}
}
}
3.斐波那契查找(Fibonacci Search)
public class FibonacciSearch {
private static final int size = 20;
public static void main(String[] args) {
int[] arr = {-4, -1, 0, 1, 2, 4, 5, 6, 7, 10};
System.out.println(fibonacciSearch(arr, -4));
}
public static int fibonacciSearch(int[] arr, int key) {
int len = arr.length;
int low = 0;
int mid = 0;
int high = len - 1;
int n = 0;
int[] f = getFib();
//找到等于或刚刚大于high的斐波那契值
while (len > f[n] - 1) {
n++;
}
//创建一个长度为f[n]-1的临时数组,超出arr长度的部分用最后一个元素补齐
int[] temp = Arrays.copyOf(arr, f[n] - 1);
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
System.out.println(Arrays.toString(temp));
while (low <= high) {
//mid = low + f[n - 1] - 1
mid = low + f[n - 1] - 1;
//f[n] = f[n - 1] + f[n - 2]
//总 = 前 + 后
if (key < temp[mid]) {
high = mid - 1;
n -= 1;
} else if (key > temp[mid]) {
low = mid + 1;
n -= 2;
} else {
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
public static int[] getFib() {
int[] f = new int[size];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < size; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
}
原文链接:https://www.cnblogs.com/songjilong/p/12236627.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-06-03
- 基础排序算法(附加java实现) 2020-06-02
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-05-29
- LeetCode 面试题53 - I. 在排序数组中查找数字 I 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash