线性查找
//线性查找
public static int seqSearch(int[] arr,int value){
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value){
return i;
}
}
return -1;
}
二分法查找（递归）
只适用于有序数组
package 算法.search;
import java.util.ArrayList;
//二分法（数组必须是有序的）
public class BinarySearch {
public static void main(String[] args) {
int array[] = {1,2,3,4,5,5,5,5,6,7,7,8,9};
//int index = binarySearch(array,0,array.length-1,5);
ArrayList<Integer> index = binarySearch2(array,0,array.length-1,5);
System.out.println(index);
}
//二分法（数组必须是有序的）
public static int binarySearch(int[] arr,int left,int right,int findVal){
if (left>right){
return -1;
}
int mid = (left + right)/2;
int midVal = arr[mid];
if (findVal > midVal){
return binarySearch(arr,mid + 1,right,findVal);
}else if (findVal < midVal){
return binarySearch(arr,left,mid - 1,findVal);
}else {
return mid;
}
}
//二分法（数组必须是有序的） 返回多个值的索引
public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
if (left>right){
return new ArrayList<Integer>();
}
int mid = (left + right)/2;
int midVal = arr[mid];
if (findVal > midVal){
return binarySearch2(arr,mid + 1,right,findVal);
}else if (findVal < midVal){
return binarySearch2(arr,left,mid - 1,findVal);
}else {
ArrayList<Integer> resIndexlist = new ArrayList<Integer>();
int temp = mid - 1;
while (true){
if (temp < 0 || arr[temp] != findVal){
break;
}
resIndexlist.add(temp);
temp -=1;
}
resIndexlist.add(mid);
temp = mid + 1;
while (true){
if (temp > arr.length - 1 || arr[temp] != findVal){
break;
}
resIndexlist.add(temp);
temp +=1;
}
return resIndexlist;
}
}
}
插值查找
规则：
- 对于数据量大，关键字分布比较怕均匀
//插值查找（数组必须是有序的）
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
if (left>right || findVal < arr[0] || findVal > arr[arr.length - 1]){
return -1;
}
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal){
return insertValueSearch(arr,mid + 1,right,findVal);
}else if (findVal < midVal){
return insertValueSearch(arr,left,mid - 1,findVal);
}else {
return mid;
}
}
斐波那契查找算法（黄金分割法）
package 算法.search;
import java.util.Arrays;
//斐波那契查找算法
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int[] array = {1,8,10,89,1000,1234};
System.out.println(fibonacciSearch(array,1000));
}
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 fibonacciSearch(int[] a,int key){
int low = 0;
int high = a.length - 1;
int k = 0;
int mid = 0;
int f[] = fib();
while (high > f[k] - 1){
k++;
}
int[] temp = Arrays.copyOf(a,f[k]);
for (int i = high + 1; 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;
}
}
你知道的越多，你不知道的越多。
有道无术，术尚可求，有术无道，止于术。
如有其它问题，欢迎大家留言，我们一起讨论，一起学习，一起进步