在java中测蹲,我們常用的查找有四種:
(1) 順序(線性)查找
(2) 二分查找/折半查找
(3) 插值查找
(4) 斐波那契查找
1.順序查找算法(線性查找)
public class SeqSearch {
public static void main(String[] args) {
int[] arr={1,3,2,6,76,34,22,15,33,78};
int result = search(arr, 2);
if(result == -1){
System.out.println("沒有找到");
} else{
System.out.println("找到了6拭病!熟尉!");
}
}
public static int search(int[] arr,int val){
int length = arr.length;
for(int i=0;i<length;i++){
if(val == arr[i]) {
return arr[i];
}
}
return -1;
}
}
很簡單弊仪,我們可以跳過熙卡。
二分查找算法
對一個有序數(shù)組進行二分查找{1,8,10,89,1000,1234},輸入一個數(shù)看看該數(shù)組是否存在此數(shù)励饵,并且求出下標(biāo)驳癌,如果沒有就提示"沒有這個數(shù)"。?對查找的數(shù)組要求是有序的役听,升序颓鲜。
遞歸
對一個有序數(shù)組進行二分查找 {1,8, 10, 89, 1000, 1234} ,輸入一個數(shù)看看該數(shù)組是否存在此數(shù)典予,并且求出下標(biāo)甜滨,如果沒有就提示"沒有這個數(shù)"。?
思路
二分查找的思路分析
- 首先確定該數(shù)組的中間的下標(biāo)
mid = (left + right) / 2 - 然后讓需要查找的數(shù) findVal 和 arr[mid] 比較
- 1 findVal > arr[mid] , 說明你要查找的數(shù)在mid 的右邊, 因此需要遞歸的向右查找
2.2 findVal < arr[mid], 說明你要查找的數(shù)在mid 的左邊, 因此需要遞歸的向左查找
2.3 findVal == arr[mid] 說明找到瘤袖,就返回
//什么時候我們需要結(jié)束遞歸.
- 找到就結(jié)束遞歸
- 遞歸完整個數(shù)組衣摩,仍然沒有找到findVal ,也需要結(jié)束遞歸 當(dāng) left > right 就需要退出
代碼實現(xiàn)
public static int binarySearch(int[] arr, int left, int right, int findVal) {
if(left > right){
return -1;
}
int mid = (right+left) / 2;
if(findVal < arr[mid]){
return binarySearch(arr,left,mid-1,findVal);
} else if(findVal > arr[mid]){
return binarySearch(arr,mid + 1,right,findVal);
} else {
return mid;
}
}
考慮將數(shù)組中存在該數(shù)值的所有索引值都找到捂敌。
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
if(left > right){
return Lists.newArrayList();
}
int mid = (right+left) / 2;
if(findVal < arr[mid]){
return binarySearch2(arr,left,mid-1,findVal);
} else if(findVal > arr[mid]){
return binarySearch2(arr,mid + 1,right,findVal);
} else {
ArrayList<Integer> arrayList = new ArrayList<>();
int temp=mid-1;
//向mid 索引值的左邊掃描艾扮,將所有滿足目標(biāo)值既琴, 的元素的下標(biāo),加入到集合ArrayList
while(temp >=0 && arr[temp] == findVal){
arrayList.add(temp--);
}
//把中間值加入
arrayList.add(mid);
temp=mid+1;
//向mid 索引值的右邊掃描泡嘴,將所有滿足目標(biāo)值甫恩, 的元素的下標(biāo),加入到集合ArrayList
while(temp <=arr.length-1 && arr[temp]==findVal ){
arrayList.add(temp++);
}
return arrayList;
}
}
非遞歸
public static void main(String[] args) {
//測試
int[] arr = {1,3, 8, 10, 11, 67, 100};
int index = binarySearch(arr, 100);
System.out.println("index=" + index);
}
public static int binarySearch(int[] arr,int target){
int right = arr.length-1;
int left = 0;
int mid;
while(left <= right){
mid = (left+right)/2;
if(arr[mid] == target){
return mid;
} else if(arr[mid] > target) {
right = mid -1;
} else {
left =mid+1;
}
}
return -1;
}
結(jié)果
插值查找法
原理介紹
插值查找原理介紹:
插值查找算法類似于二分查找酌予,不同的是插值查找每次從自適應(yīng)mid處開始查找填物。
將折半查找中的求mid 索引的公式 , low 表示左邊索引left, high表示右邊索引right.?key 就是前面我們講的 findVal
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;
/插值索引/?對應(yīng)前面的代碼公式:
int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
對比二分
對于數(shù)據(jù)量較大,關(guān)鍵字分布比較均勻的查找表來說霎终,采用插值查找, 速度較快.
關(guān)鍵字分布不均勻的情況下,該方法不一定比折半查找要好
代碼演示
//編寫插值查找算法
//說明:插值查找算法升薯,也要求數(shù)組是有序的
/**
*
* @param arr 數(shù)組
* @param left 左邊索引
* @param right 右邊索引
* @param findVal 查找值
* @return 如果找到莱褒,就返回對應(yīng)的下標(biāo),如果沒有找到涎劈,返回-1
*/
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
System.out.println("插值查找次數(shù)~~");
//注意:findVal < arr[0] 和 findVal > arr[arr.length - 1] 必須需要
//否則我們得到的 mid 可能越界
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
// 求出mid, 自適應(yīng)
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal) { // 說明應(yīng)該向右邊遞歸
return insertValueSearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 說明向左遞歸查找
return insertValueSearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
斐波那契(黃金分割法)查找算法(有序數(shù)組)
查找基本介紹
黃金分割點是指把一條線段分割為兩部分广凸,使其中一部分與全長之比等于另一部分與這部分之比。取其前三位數(shù)字的近似值是0.618蛛枚。由于按此比例設(shè)計的造型十分美麗谅海,因此稱為黃金分割,也稱為中外比蹦浦。這是一個神奇的數(shù)字扭吁,會帶來意向不大的效果。
斐波那契數(shù)列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}發(fā)現(xiàn)斐波那契數(shù)列的兩個相鄰數(shù)的比例盲镶,無限接近 黃金分割值0.618侥袜。
斐波那契(黃金分割法)原理
斐波那契查找原理與前兩種相似,僅僅?改變了中間結(jié)點(mid)的位置溉贿,mid不?再是中間或插值得到枫吧,而是位于黃金分?割點附近,即mid=low+F(k-1)-1?(F代表斐波那契數(shù)列)宇色,如下圖所示
對F(k-1)-1的理解:
由斐波那契數(shù)列 F[k]=F[k-1]+F[k-2]的性質(zhì)九杂,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 。該式說明:只要順序表的長度為F[k]-1宣蠕,則可以將該表分成長度為F[k-1]-1和F[k-2]-1的兩段例隆,即如上圖所示。從而中間位置為mid=low+F(k-1)-1
類似的植影,每一子段也可以用相同的方式分割
但順序表長度n不一定剛好等于F[k]-1裳擎,所以需要將原來的順序表長度n增加至F[k]-1。這里的k值只要能使得F[k]-1恰好大于或等于n即可思币,由以下代碼得到,順序表長度增加后鹿响,新增的位置(從n+1到F[k]-1位置)羡微,都賦為n位置的值即可。
代碼實現(xiàn)
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int [] arr = {1,8, 10, 89, 1000, 1234};
System.out.println("index=" + fibSearch(arr, 189));// 0
}
//因為后面我們mid=low+F(k-1)-1惶我,需要使用到斐波那契數(shù)列妈倔,因此我們需要先獲取到一個斐波那契數(shù)列
//非遞歸方法得到一個斐波那契數(shù)列
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;
}
//編寫斐波那契查找算法
//使用非遞歸的方式編寫算法
/**
*
* @param a 數(shù)組
* @param key 我們需要查找的關(guān)鍵碼(值)
* @return 返回對應(yīng)的下標(biāo),如果沒有-1
*/
public static int fibSearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
int k = 0; //表示斐波那契分割數(shù)值的下標(biāo)
int mid = 0; //存放mid值
int f[] = fib(); //獲取到斐波那契數(shù)列
//獲取到斐波那契分割數(shù)值的下標(biāo)
while(high > f[k] - 1) {
k++;
}
//因為 f[k] 值 可能大于 a 的 長度绸贡,因此我們需要使用Arrays類盯蝴,構(gòu)造一個新的數(shù)組,并指向temp[]
//不足的部分會使用0填充
int[] temp = Arrays.copyOf(a, f[k]);
//實際上需求使用a數(shù)組最后的數(shù)填充 temp
//舉例:
//temp = {1,8, 10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
for(int i = high + 1; i < temp.length; i++) {
temp[i] = a[high];
}
// 使用while來循環(huán)處理听怕,找到我們的數(shù) key
while (low <= high) { // 只要這個條件滿足捧挺,就可以找
mid = low + f[k - 1] - 1;
if(key < temp[mid]) { //我們應(yīng)該繼續(xù)向數(shù)組的前面查找(左邊)
high = mid - 1;
//為甚是 k--
//說明
//1. 全部元素 = 前面的元素 + 后邊元素
//2. f[k] = f[k-1] + f[k-2]
//因為 前面有 f[k-1]個元素,所以可以繼續(xù)拆分 f[k-1] = f[k-2] + f[k-3]
//即 在 f[k-1] 的前面繼續(xù)查找 k--
//即下次循環(huán) mid = f[k-1-1]-1
k--;
} else if ( key > temp[mid]) { // 我們應(yīng)該繼續(xù)向數(shù)組的后面查找(右邊)
low = mid + 1;
//為什么是k -=2
//說明
//1. 全部元素 = 前面的元素 + 后邊元素
//2. f[k] = f[k-1] + f[k-2]
//3. 因為后面我們有f[k-2] 所以可以繼續(xù)拆分 f[k-1] = f[k-3] + f[k-4]
//4. 即在f[k-2] 的前面進行查找 k -=2
//5. 即下次循環(huán) mid = f[k - 1 - 2] - 1
k -= 2;
} else { //找到
//需要確定,返回的是哪個下標(biāo)
if(mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
結(jié)束