減治法在查找算法中的應(yīng)用

折半查找：(時間復(fù)雜度O(log以2為底n的對數(shù)))

對于有序數(shù)組的查找來說，折半查找是一種非常高效的算法，其基本原理為：比較查找鍵k和數(shù)組中間元素a[m]，如果相等，算法結(jié)束；如果k<a[m]，對數(shù)組前半部分執(zhí)行操作；如果k>a[m]，對數(shù)組后半部分執(zhí)行操作。

?

public class Main {static int k = 89;static int[] a = {17, 29, 34, 45, 68, 89, 90};public static void main(String[] args) {int l = 0;int r = a.length-1;System.out.println(f(l, r));}private static int f(int l, int r) {while (l <= r) {int m = (l+r)/2;if (k == a[m]) {return m;} else if (k < a[m]) {return f(l, m-1);} else {return f(m+1, r);}}return -1;} }

發(fā)現(xiàn)問題：對于依賴鍵值操作的查找算法來說，折半查找已經(jīng)是最優(yōu)的查找算法了，但是還是有些算法具有更優(yōu)良的平均效率

解決思路：插值查找，散列查找（散列法甚至不需要輸入數(shù)組是有序的）

插值查找：不同于折半查找總是把查找值和給定有序數(shù)組的中間元素比較（將問題規(guī)模削減一半），差值查找更像是在字典中查字的形式，如果我們找“班”這個字，那么我們一定先找“B”字母的區(qū)域，我們不會去從字典中間區(qū)域開始。準(zhǔn)確來說，插值查找同樣采用比較的方式，但是它考慮了查找鍵的值。

實際上對于較小數(shù)據(jù)的查找，折半會更好；而對于大數(shù)據(jù)量而言，插值查找則更值得考慮。

總結(jié)

以上是生活随笔為你收集整理的减治法在查找算法中的应用（JAVA）--折半查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。