二分法

2021-01-14 啊哈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]上使用二分法。

相關焦點

  • 二分法思維
    二分法思維是一種哲學思維，是指把一樣東西看作兩個部分來看待。比如一個人做一件事情，不是做對了，就是做錯了。買一個包包，不是買的假貨，就是買的真貨。        答案:  1.有必要  2.沒必要        類似上面的例題，每個提問都只有兩個答案的這種方式，就叫二分法思維。
  • 武術'二分法'
    但進一步深入探究相關概念後,我認為應該把「二分法」作為一種隱性的分類方法加以解釋和重視。　　1.2質疑、妥協、探索和爭論　　對於武術「二分法」,也有一些學者發現其存在問題。如楊建營[6]指出:單從字面上講,競技即比賽,競技武術即比賽的武術。
  • JAVA編程——二分法查找
    一、二分法檢索過程二分法檢索（binary search）又稱折半檢索，二分法檢索的基本思想是設數組中的元素從小到大有序地存放在數組（array）中（註：二分法查找的關鍵，首先數組元素必須從小到大有序排列），（1）首先將給定值 key 與數組中間位置上元素的關鍵碼(key)比較，如果相等，則檢索成功
  • 著作權法中的 「思想與表達二分法」
    原標題：著作權法中的 「思想與表達二分法」 在著作權法中，「思想與表達二分法」是一項重要原則。該原則將作品分為思想與表達兩方面，著作權法只保護對於思想觀念的獨創性表達，而不保護思想觀念本身。
  • 面試手撕算法系列:二分法
    最近春招開始了，面試面著面著一言不合就開始手撕代碼手撕就手撕，接下來我打算寫幾個專題講講面試中手撕的常見題目 這些都是LeetCode上有的題目 手撕無非就是 樹、鍊表、二分、字符串這些常用的數據結構二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索算法。
  • 新民晚報:「二分法」邏輯
    原標題：「二分法」邏輯 最近吉林省紀委發布消息稱，吉林省第十二屆人民代表大會常務委員會委員、農業與農村委員會主任委員藍軍，涉嫌嚴重違紀，目前正在接受組織調查。 藍軍廣為人知，是因為他當年離任松原書記的時候，當地出現了「千人相送」的盛大場面，那個時候，藍書記頭上頂著的是「好官」的光環。
  • 武林至尊,寶刀屠龍——略談易經中的陰陽二分法
    這把陰陽寶刀就是陰陽二分法。，這是陰陽二分法的基礎應用方法。易經思想中所強調的「安而不忘危，存而不忘亡，治而不忘亂」等觀點就是陰陽二分法的具體體現，要求管理者能夠居安思危、見存知亡、見治不忘亂，永遠從正反兩個方面去看待問題，解決問題。《道德經》中提到的「禍兮福之所倚；福兮禍之所伏」的福禍相依的觀點同樣也是陰陽二分法的反映。
  • ——從思想與表達「二分法」談起
    在著作權法中，思想與表達二分法是一項重要原則，並對著作權的保護意義重大。一、思想與表達二分法原則的含義與規定思想與表達二分法原則將作品分為思想與表達兩方面，著作權法只保護對於思想觀念的獨創性表達，而不保護思想觀念本身。
  • 漫畫:二分法深度剖析(第二講)
    繼續為大家分享二分法系列篇的內容，看一道比較簡單的題目。這道題目是比較簡單，但我認為同時也是非常經典，建議大家掌握！第69題：實現 int sqrt(int x) 函數計算並返回 x 的平方根，其中 x 是非負整數。
  • 教學研討|用二分法求方程的近似解·教案·課件
    然後推廣為一般方程與相應函數的情形；第二步，在用二分法求方程近似解的過程中，通過函數圖像和性質來研究方程的解，體現方程和函數的關係；第三步，在函數模型的應用過程中，通過函數模型以及模型的求解，更全面的體現函數與方程的關係，逐步建立起函數與方程的聯繫。
  • 算法分析——二分法查詢
    題目 假設在一個已經排好序的有序序列(N個元素，升序排列)，使用二分法進行查詢（使用遞歸實現） 原文收錄在 公眾號 慕陽源碼 感興趣或者有問題的小夥伴 聯繫我哦
  • 算法競賽小專題系列(1):二分法、三分法
    清華大學出版社二分法和三分法是算法競賽中常見的算法思路，本文介紹了它們的理論背景、模板代碼、典型題目。1. 二分法的理論背景在《計算方法》教材中，關於非線性方程的求根問題，有一種是二分法。整數二分典型題目  上面給出的二分法代碼bin_search()，處理的是簡單的數組查找問題。從這個例子，我們能學習到二分法的思想。　　在用二分法的典型題目中，主要是用二分法思想來進行判定。
  • 高明的人:用三分法考慮,用二分法做抉擇,用一分法去執行
    它們分別是：一分法、二分法和三分法。一分法，無論任何事情，只要聽到或者看到就會輕易下決定，不經過思慮就採取「相信」或者「不信」的態度。這就是一分法的思維方式。二分法與一分法就有了很明顯的區別。二分法是一切事情，不會輕易下決定，會經過認真考慮，然後做出判斷。只要決定下來了，那就不會再改變。三分法，更加讓人摸不著頭腦。
  • 程式設計師挑戰:如何讓一個技術小白搞懂二分法檢索?
    我敢打賭，即使他們沒有任何技術背景，最後他們也能開發出一個二分法檢索的算法，並且理解這個概念。傳統意義上的二分法檢索問題以下是Geeks for Geeks上給出的二分法檢索的定義：「給定一個包含n個元素的排序數組arr[]，編寫一個函數來搜索arr[]中的給定元素x。」即使我是軟體工程專業，但讀到這裡時依然會頭疼。
  • 例析二分法的應用--中國數字科技館
    文章數 例析二分法的應用2009-02-07 14:50:59
  • 人權和公民權二分法的思想源流與規範演變
    因此，英國式自由主義與法國式共和主義共同為宣言中的二分法提供著思想基礎。宣言糅合了自然權利、社會契約、國民主權等近代啟蒙觀念以及一定程度的社會主義，從而有效協調人和公民兩種身份。幾乎所有當代權利清單都可以在人權和公民權二分法中找到其思想淵源，當代人權文件所採取的二分法、三分法乃至四分法也都受惠於它。
  • 三個步驟,助你抓住高中數學「二分法求方程根近似值」問題的本質
    在實際應用中，有些方程(如非線性方程)要麼求根公式複雜而不實用，要麼根本不存在求根公式，此時就要用到近似求解方法，如二分法、牛頓迭代法等數值法。因此，在所學知識和方法基礎上，能結合實際應用，熟練地應用近似求解的意識、方法與能力去解決問題，具有重要的實用意義。本文將講述高中階段要求掌握的二分法求方程式根的近似值的方法與技巧。1.
  • 「事實價值」二分法讓你重新認識品牌傳播背後的真相!
    小僧從「事實-價值」二分法模型來為你詳細解析。從「事實-價值」二分法模型理解傳播事實與價值二分法是現代道德哲學與倫理學的基本前提，其最早提出者休謨認為，「是」的命題無法直接推導「應當」的命題。「是」指向事實知識，「應當」則指向價值知識，「是」不必然指向「應當」。
  • 面試向算法 - 二分法專題(二)
    在 《二分法（一）》當中我們已經分別講解了：那麼，本篇的主要內容即是對剩下的四種應用進行深入分析。最大/最小平均值(max/min average)注意：搭配 B 站視頻更香奧！而上述通過二分法能夠處理的最優化問題需要滿足：值域 滿足某種特殊的單調性。
  • 解析二分法求方程f(x)=0在區間「a,b」內近似值的解題步驟
    取[a，b]的中點x=1/2 (a+b)，將區間一分為二用二分法求方程的近似解時會給出近似值與精確值的差的絕對值的範圍，即給出精確度的大小；在使用二分法求方程的近似解時還要找到這個方程的解存在的區間，因為並不是所有的題都給出區間；找到該方程的區間後，求出這個區間的中點，將區間分為兩個區間，方程的解只能在這個區間中的一個區間上，這樣就縮小了區間的範圍