常見幾大查找算法整理

在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ù)"。?


image

思路

二分查找的思路分析

  1. 首先確定該數(shù)組的中間的下標(biāo)
    mid = (left + right) / 2
  2. 然后讓需要查找的數(shù) findVal 和 arr[mid] 比較
  3. 1 findVal > arr[mid] , 說明你要查找的數(shù)在mid 的右邊, 因此需要遞歸的向右查找
    2.2 findVal < arr[mid], 說明你要查找的數(shù)在mid 的左邊, 因此需要遞歸的向左查找
    2.3 findVal == arr[mid] 說明找到瘤袖,就返回

//什么時候我們需要結(jié)束遞歸.

  1. 找到就結(jié)束遞歸
  2. 遞歸完整個數(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é)果

image

插值查找法

原理介紹

插值查找原理介紹:

插值查找算法類似于二分查找酌予,不同的是插值查找每次從自適應(yīng)mid處開始查找填物。
將折半查找中的求mid 索引的公式 , low 表示左邊索引left, high表示右邊索引right.?key 就是前面我們講的 findVal

image

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ù)列)宇色,如下圖所示

image

對F(k-1)-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

  2. 類似的植影,每一子段也可以用相同的方式分割

  3. 但順序表長度n不一定剛好等于F[k]-1裳擎,所以需要將原來的順序表長度n增加至F[k]-1。這里的k值只要能使得F[k]-1恰好大于或等于n即可思币,由以下代碼得到,順序表長度增加后鹿响,新增的位置(從n+1到F[k]-1位置)羡微,都賦為n位置的值即可。

image

代碼實現(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é)束

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末尿瞭,一起剝皮案震驚了整個濱河市闽烙,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌声搁,老刑警劉巖黑竞,帶你破解...
    沈念sama閱讀 218,858評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異疏旨,居然都是意外死亡很魂,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,372評論 3 395
  • 文/潘曉璐 我一進店門檐涝,熙熙樓的掌柜王于貴愁眉苦臉地迎上來遏匆,“玉大人,你說我怎么就攤上這事骤铃±辏” “怎么了?”我有些...
    開封第一講書人閱讀 165,282評論 0 356
  • 文/不壞的土叔 我叫張陵惰爬,是天一觀的道長喊暖。 經(jīng)常有香客問我,道長撕瞧,這世上最難降的妖魔是什么陵叽? 我笑而不...
    開封第一講書人閱讀 58,842評論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮丛版,結(jié)果婚禮上巩掺,老公的妹妹穿的比我還像新娘。我一直安慰自己页畦,他們只是感情好胖替,可當(dāng)我...
    茶點故事閱讀 67,857評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般独令。 火紅的嫁衣襯著肌膚如雪端朵。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,679評論 1 305
  • 那天,我揣著相機與錄音,去河邊找鬼场绿。 笑死,一個胖子當(dāng)著我的面吹牛站刑,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播,決...
    沈念sama閱讀 40,406評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼乘凸!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起累榜,我...
    開封第一講書人閱讀 39,311評論 0 276
  • 序言:老撾萬榮一對情侶失蹤翰意,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后信柿,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,767評論 1 315
  • 正文 獨居荒郊野嶺守林人離奇死亡醒第,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,945評論 3 336
  • 正文 我和宋清朗相戀三年渔嚷,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片稠曼。...
    茶點故事閱讀 40,090評論 1 350
  • 序言:一個原本活蹦亂跳的男人離奇死亡形病,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出霞幅,到底是詐尸還是另有隱情漠吻,我是刑警寧澤,帶...
    沈念sama閱讀 35,785評論 5 346
  • 正文 年R本政府宣布司恳,位于F島的核電站途乃,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏扔傅。R本人自食惡果不足惜耍共,卻給世界環(huán)境...
    茶點故事閱讀 41,420評論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望猎塞。 院中可真熱鬧试读,春花似錦、人聲如沸荠耽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,988評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至倘屹,卻和暖如春银亲,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背唐瀑。 一陣腳步聲響...
    開封第一講書人閱讀 33,101評論 1 271
  • 我被黑心中介騙來泰國打工群凶, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人哄辣。 一個月前我還...
    沈念sama閱讀 48,298評論 3 372
  • 正文 我出身青樓请梢,卻偏偏與公主長得像,于是被迫代替她去往敵國和親力穗。 傳聞我的和親對象是個殘疾皇子毅弧,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,033評論 2 355

推薦閱讀更多精彩內(nèi)容