二分法

2021-03-02 啊哈CNUHS

        二分法是什麼呢？百度上的定義是：「對於區間[a,b]上連續不斷且f(a)·f(b)<0的函數y=f(x)，通過不斷地把函數f(x)的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫二分法。」

        這個定義比較複雜，我們把它分成幾部分來看。

一、二分法的用途

        二分法可以讓我們在一個區間[a,b]上取得函數f(x)的一個零點的近似值。

二、使用二分法的條件

        想要在區間[a,b]上使用二分法求零點，我們必須要保證區間[a,b]上有零點。想起來去年Dijkstra對我說，你看這個二分法他蠢的一批，萬一區間裡沒有零點怎麼辦？我當時覺得好有道理。今天才知道原來二分法要滿足「零點存在定理」。所謂零點存在定理，就是說函數在區間[a,b]上連續不斷且f(a)·f(b)<0。

        為什麼滿足零點存在定理就可以使用二分法呢？因為既然f(a)·f(b)<0，那麼f(a)和f(b)必定是一正一負。又因為函數圖像連續不斷，所以函數值由正變負或由負變正，必然會經過x軸，使得區間[a,b]上存在零點。

三、二分法的實現過程

        二分法是怎麼實現的呢？簡單地說，每次取區間[a,b]的中點，判斷(a+b)/2是不是零點。如果是，那麼我們就直接找到了零點，算法結束。如果不是，那麼我們就要分情況討論。如果f((a+b)/2)與f(a)同號，那麼區間[(a+b)/2,b]滿足零點存在定理，也就是說，零點存在於區間[(a+b)/2,b]上，我們可以繼續在區間[(a+b)/2,b]上使用二分法；否則，f((a+b)/2)必定與f(b)同號，那麼同理我們可以在區間[a,(a+b)/2]上使用二分法。

相關焦點

  • 諸葛亮的二分法遊戲
    二分法是數學裡非常經典的方法,不管是初等數學,高等數學,計算數學,幾乎都有他的影子，學計算機的朋友就更不會陌生。
  • 「二分法」中數學思想的提煉
    ，經歷求近似解的過程，總結出「二分法」的一般程序．到底是：「猜價格」遊戲不具有「二分法」的必要因素與必要形式（所以，現實情景與數學內容必然是兩張皮），還是教學沒有組織學生去建立聯繫，教師沒有發揮出主導作用？報刊上存在專家的不同聲音，你是什麼意見？ 「猜價格」遊戲與「二分法」的聯繫，不僅是「一半、一半又一半」類似，下面是一個數學化的提練過程：
  • 二分法題型小結
    學好算法沒有捷徑，最好的捷徑就是多刷題，並且跳出舒適區，每道題都要尋找最優解，也不能老是做那些你自己比較擅長的題，不定期更新 Leetcode 的題，每道題都會給出多種解法以及最優解在刷題的過程中，二分法用的還是挺多的，有時候超時了往往是你沒有用上二分法，今天我就來稍微總結下用的最多的三種二分法搜索。
  • 著作權法中的 「思想與表達二分法」
    原標題：著作權法中的 「思想與表達二分法」 在著作權法中，「思想與表達二分法」是一項重要原則。該原則將作品分為思想與表達兩方面，著作權法只保護對於思想觀念的獨創性表達，而不保護思想觀念本身。
  • 著作權法中的「思想與表達二分法」
    「思想與表達二分法」是著作權法中一項重要原則。它將作品分為思想與表達兩方面，著作權只保護對於思想觀念的獨創性表達，而不保護思想觀念本身。圖片來源於網絡根據「思想與表達二分法」，在涉及著作權的侵權案件中，需要判斷的是被告未經許可使用的究竟是原告作品中的思想觀念，還是思想觀念的表達。而思想和表達的分界線並不是很清晰。
  • 面試手撕算法系列:二分法
    最近春招開始了，面試面著面著一言不合就開始手撕代碼手撕就手撕，接下來我打算寫幾個專題講講面試中手撕的常見題目 這些都是LeetCode上有的題目 手撕無非就是 樹、鍊表、二分、字符串這些常用的數據結構二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索算法。
  • 二分法其實很簡單,為什麼老是寫不對!!
    作者丨代碼隨想錄 來源丨代碼隨想錄 （code_thinking）相信很多人對二分法是又愛又恨，愛是在於它思想簡單
  • 漫畫:二分法深度剖析(第二講)
    使用二分法來完成平方根還是比較容易被想到的，在有限的「區間」中，每次通過篩選一半的元素，到最終只剩下一個數（收斂），這個數就是題目要求的取整的平方根整數。根據之前說過的二分法模板，要使用二分法，我們當然要找到Left，Right，Mid，那在這裡，Mid 自然被作為最終我們要找的平方根的值（不像上一道題，Mid是作為速度，不太容易被想到），而 Left 和 Right，我們採用 1 和 x/2。
  • 遍歷,二分法:排序,紅黑樹,斯特拉森算法
    幾個「最」，說明人對極值更敏感:(電腦一般情況下，要麼從頭到尾遍歷，要麼使用二分法。電腦算法的優化，很多就是把遍歷算法變成二分法的遞歸。歸併排序，則是典型的二分法。16個數，一分為二每組8個，二分為4每組4個，三分為8每組2個，四分為16每組1個。每組1個的時候也就無所謂順序了。然後把它們兩兩一組的合併起來，只需要一次比較，小的在前，大的在後，也就排好了。
  • 面試向算法 - 二分法專題(一)
    二分法是一種隨處可見卻又非常精妙的算法，我們最熟知的用法是在一個有序數組中查找某個 target 是否存在。初學二分法的同學可能會被各種邊界情況、不同寫法、是開區間還是閉區間等細節弄糊塗，以至於捨本逐末。其實並不需要如此，我們只需要記住一種最方便的寫法並理解它即可。二分法主題分為兩篇，本篇為第一篇。
  • 算法競賽小專題系列(1):二分法、三分法
    清華大學出版社二分法和三分法是算法競賽中常見的算法思路，本文介紹了它們的理論背景、模板代碼、典型題目。1. 二分法的理論背景在《計算方法》教材中，關於非線性方程的求根問題，有一種是二分法。整數二分典型題目  上面給出的二分法代碼bin_search()，處理的是簡單的數組查找問題。從這個例子，我們能學習到二分法的思想。　　在用二分法的典型題目中，主要是用二分法思想來進行判定。
  • 公司決議不成立的質疑與二分法的回歸
    總體而言，公司決議不成立沒有獨立存在的必要，應當回歸《公司法》第22條確立的二分法。具有嚴重程序瑕疵的公司決議應通過類推適用《公司法》第22條第1款而評價為無效。《公司法解釋四》頒行前，實務上多是在二分法的框架下填補《公司法》第22條第2款的漏洞，即對某些重大的程序瑕疵，判決其無效， 這說明二分法似乎更受司法實務的青睞。不僅如此，二分法似乎也更符合《公司法》立法者的意思。之所以作此論斷，是因為2005年《公司法》修正時日本、韓國已經完成了成文法層面二分法向三分法的轉變， 我國臺灣地區實務與學理上也已經認可公司決議不成立的獨立地位。
  • 工作總是煩躁焦慮不順心,你肯定沒聽過控制二分法
    02、控制二分法我們之所以會在工作中感到煩躁和焦慮，究其原因，絕大多數情況是因為事情超出了控制範圍，以至於結果不如預期，你就會自然而然地生出「煩死了」的情緒！談到「控制」一詞，就不得不提及斯多葛哲學裡最著名的「控制二分法」了。
  • 三個步驟,助你抓住高中數學「二分法求方程根近似值」問題的本質
    本文將講述高中階段要求掌握的二分法求方程式根的近似值的方法與技巧。1. 基本問題說明二分法，又稱分半法，是一種方程式根的近似值求法。對於區間[a, b]上連續不斷且f(a)·f(b)<0的函數y=f(x)，通過不斷地把函數f(x)的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫做二分法(bisection,如圖)。
  • 面試向算法 - 二分法專題(二)
    在 《二分法（一）》當中我們已經分別講解了：那麼，本篇的主要內容即是對剩下的四種應用進行深入分析。最大/最小平均值(max/min average)注意：搭配 B 站視頻更香奧！而上述通過二分法能夠處理的最優化問題需要滿足：值域 滿足某種特殊的單調性。
  • 使用Python和C語言實現二分法查找(折半查找)
    二分法查找算法的原理如下：1、 如果待查對象為空返回-1，表示查找不到目標元素2、 如果待查序列不為空，則將中間元素與要查找的目標元素進行匹配看是否相等，如果相等表示 查找成功，返回該中間元素的索引如果不相等再比較這兩個元素的大小
  • 佔星英語總結(2):星座四元素、三特質、二分法以及古代天文學
    星座陰陽分法（二分法）的表達屬性：Polarity [plrti]陽性星座：Masculine Sign陰性星座：Feminine Signpolarity 實為極性與反向性的意思
  • 必看系列7——函數與方程、零點、二分法等基礎知識大梳理
    （教材截取）五、二分法
  • 不說廢話,直接給出verilog代碼for二分法查找
    上一篇文章IC君介紹了二進位搜索算法（二分法查找）在實際電路中的應用，而且文末也給出了一個電路設計的spec，可惜也沒人給出代碼或者電路，沒辦法只能IC君自己上了Linux 的創始人 Linus 曾經說過：Talk is cheap. Show me the code.
  • 懂Excel輕鬆入門Python數據分析包pandas(二十八):二分法查找
    後來才發現，原來不是 Python 數據處理厲害，而是他有數據分析神器—— pandas前言Excel 中的 vlookup 函數有一個模糊查找選項，其內在原理為二分法查找，在 pandas 中同樣有一樣功能的方法。