查找--斐波那契查找(Java)

来源:https://www.cnblogs.com/guizimo/archive/2020/07/23/13369245.html
-Advertisement-
Play Games

查找--斐波那契查找(Java) 博客說明 文章所涉及的資料來自互聯網整理和個人總結,意在於個人學習和經驗彙總,如有什麼地方侵權,請聯繫本人刪除,謝謝! 介紹 黃金分割點是指把一條線段分割為兩部分,使其中一部分與全長之比等於另一部分與這部分之比。取其前三位數字的近似值是0.618。 斐波那契數列 { ...


查找--斐波那契查找(Java)

博客說明

文章所涉及的資料來自互聯網整理和個人總結,意在於個人學習和經驗彙總,如有什麼地方侵權,請聯繫本人刪除,謝謝!

介紹

黃金分割點是指把一條線段分割為兩部分,使其中一部分與全長之比等於另一部分與這部分之比。取其前三位數字的近似值是0.618。

斐波那契數列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 發現斐波那契數列的兩個相鄰數 的比例,無限接近 黃金分割值0.618

思路

利用斐波那契數列的特性來查找mid

代碼

package cn.guizimo.search;

import java.util.Arrays;

/**
 * @author guizimo
 * @date 2020/7/23 10:06 下午
 */
public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 100, 1000};
        System.out.println(fibSearch(arr,8));
    }

    //斐波那契數列
    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 fibSearch(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;
    }
}

感謝

尚矽谷

萬能的網路

以及勤勞的自己
關註公眾號: 歸子莫,獲取更多的資料,還有更長的學習計劃


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一,效果圖。 二,代碼。 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>CSS 偽類</title> <style> a:link { color: #FF0000; } /* unvisited link */ a:visi ...
  • 前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 前面幾節,我們一起學習了演算法的複雜度如何分析,並從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了演算法的複雜度,在我們表示覆雜度的 ...
  • //記錄滑鼠按下 public static bool MouseBtnIsDown = false; //截圖起始坐標 public static Point StartPoint; //截圖的長寬 double width = 0; double height = 0; //滑鼠按下事件 pub ...
  • 前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 上一節,我們從最壞、平均、最好三種情況分析了演算法的複雜度,得出結論,通常來說,使用最壞情況來評估演算法的複雜度完全夠用了。 但是,有些演算法是 ...
  • 《Microsoft .NET 企業級應用架構設計》 [作者] (意) Dino Esposito (意) Andrea Saltarello[譯者] (中) 陳黎夫[出版] 人民郵電出版社[版次] 2010年06月 第1版[印次] 2010年06月 第1次 印刷[定價] 69.00元 【前言】 ( ...
  • GitHub(國內)加速 Windows的加速方式 大家知道GitHub這個網站,但是由於GitHub是國外的網站,國外伺服器等諸多原因導致國內訪問GitHub非常慢(其實最主要的原因是GitHub的分發加速網路的功能變數名稱遭到dns污染),clone、push、pull倉庫有時只有幾KB的速度,而且動不 ...
  • 數據結構--哈希表(Java) 博客說明 文章所涉及的資料來自互聯網整理和個人總結,意在於個人學習和經驗彙總,如有什麼地方侵權,請聯繫本人刪除,謝謝! 介紹 哈希表底層是數組加鏈表或者是數組加二叉樹,一個數組裡面有多個鏈表,通過散列函數來提高效率 代碼 package cn.guizimo.hash ...
  • 今天不知咋回事使用easywechat的內容安全api,不知咋回事.之前還可以使用的這些天突然報這個錯,也不知道是不是因為升級還是與其他的衝突, 那怎麼辦呢,還是用下原生的介面,在這裡我獲取的token方法還是easywechat的方式 $miniProgram = ZFac::miniProgra ...
一周排行
    -Advertisement-
    Play Games
  • 通過WPF的按鈕、文本輸入框實現了一個簡單的SpinBox數字輸入用戶組件並可以通過數據綁定數值和步長。本文中介紹了通過Xaml代碼實現自定義組件的佈局,依賴屬性的定義和使用等知識點。 ...
  • 以前,我看到一個朋友在對一個系統做初始化的時候,通過一組魔幻般的按鍵,調出來一個隱藏的系統設置界面,這個界面在常規的菜單或者工具欄是看不到的,因為它是一個後臺設置的關鍵界面,不公開,同時避免常規用戶的誤操作,它是作為一個超級管理員的入口功能,這個是很不錯的思路。其實Winform做這樣的處理也是很容... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他的程式每次關閉時就會自動崩潰,一直找不到原因讓我幫忙看一下怎麼回事,這位朋友應該是第二次找我了,分析了下 dump 還是挺經典的,拿出來給大家分享一下吧。 二:WinDbg 分析 1. 為什麼會崩潰 找崩潰原因比較簡單,用 !analyze -v 命 ...
  • 在一些報表模塊中,需要我們根據用戶操作的名稱,來動態根據人員姓名,更新報表的簽名圖片,也就是電子手寫簽名效果,本篇隨筆介紹一下使用FastReport報表動態更新人員簽名圖片。 ...
  • 最新內容優先發佈於個人博客:小虎技術分享站,隨後逐步搬運到博客園。 創作不易,如果覺得有用請在Github上為博主點亮一顆小星星吧! 博主開始學習編程於11年前,年少時還只會使用cin 和cout ,給單片機點點燈。那時候,類似async/await 和future/promise 模型的認知還不是 ...
  • 之前在阿裡雲ECS 99元/年的活動實例上搭建了一個測試用的MINIO服務,以前都是直接當基礎設施來使用的,這次準備自己學一下S3相容API相關的對象存儲開發,因此有了這個小工具。目前僅包含上傳功能,後續計劃開發一個類似圖床的對象存儲應用。 ...
  • 目錄簡介快速入門安裝 NuGet 包實體類User資料庫類DbFactory增刪改查InsertSelectUpdateDelete總結 簡介 NPoco 是 PetaPoco 的一個分支,具有一些額外的功能,截至現在 github 星數 839。NPoco 中文資料沒多少,我是被博客園群友推薦的, ...
  • 前言 前面使用 Admin.Core 的代碼生成器生成了通用代碼生成器的基礎模塊 分組,模板,項目,項目模型,項目欄位的基礎功能,本篇繼續完善,實現最核心的模板生成功能,並提供生成預覽及代碼文件壓縮下載 準備 首先清楚幾個模塊的關係,如何使用,簡單畫一個流程圖 前面完成了基礎的模板組,模板管理,項目 ...
  • 假設需要實現一個圖標和文本結合的按鈕 ,普通做法是 直接重寫該按鈕的模板; 如果想作為通用的呢? 兩種做法: 附加屬性 自定義控制項 推薦使用附加屬性的形式 第一種:附加屬性 創建Button的附加屬性 ButtonExtensions 1 public static class ButtonExte ...
  • 在C#中,委托是一種引用類型的數據類型,允許我們封裝方法的引用。通過使用委托,我們可以將方法作為參數傳遞給其他方法,或者將多個方法組合在一起,從而實現更靈活的編程模式。委托類似於函數指針,但提供了類型安全和垃圾回收等現代語言特性。 基本概念 定義委托 定義委托需要指定它所代表的方法的原型,包括返回類 ...