在MySQL中完成二分查找的具體教程。本站提示廣大學習愛好者：（在MySQL中完成二分查找的具體教程）文章只能為提供參考，不一定能成為您想要的結果。以下是在MySQL中完成二分查找的具體教程正文
給定一個升序分列的天然數數組，數組中包括反復數字，例如：[1,2,2,3,4,4,4,5,6,7,7]。成績：給定隨意率性天然數，對數組停止二分查找，前往數組准確的地位，給出函數完成。注：持續雷同的數字，前往第一個婚配地位照樣最初一個婚配地位，由函數傳入參數決議。
我為何會出這道標題？
二分查找在數據庫內核完成中異常主要
在數據庫的內核完成中，二分查找是一個異常主要的邏輯，簡直99%以上的SQL語句(一切索引上的規模掃描/等值查詢/Unique查詢等)，都邑應用到二分查找停止數據的定位。
斟酌一個數據庫表t1(a int primary key, b int)，表上的b字段有一個B+樹索引，表中記載的b字段取值，就是標題中的[1,2,2,3,4,4,4,5,6,7,7]序列。此時，給定以下的兩條查詢語句，就是應用到了分歧的二分查找邏輯：
SQL1：
select * from t1 where b > 4;
SQL2：
select * from t1 where b >= 4;
針對SQL1，索引的二分查找，就須要跳過一切的4，從最初一個4以後開端前往一切記載；針對SQL2，二分查找就須要定位到第一個4，然後次序讀取一切記載。
除此以外，針對數據庫中其他的查詢邏輯，二分查找還須要附帶更多的功效，例如：
SQL3：
select * from t1 where b < 2;
SQL4：
select * from t1 where b <= 2;
因為數據庫索引同時支撐反向掃描，是以SQL3、SQL4的語句，都可使用索引反向掃描。反向掃描時，SQL3須要定位到索引中的第一個2；而SQL4，則須要定位到索引的最初一個2，然後開端反向前往知足查詢前提的索引記載。
二分查找在法式設計中，是一個非常基本而且易錯的功效
第一個真正准確的二分查找算法，在第一個二分查找完成以後的12年，才被揭橥出來。經由過程Google，輸出Binary Search或許是二分查找症結字，有年夜量的相干的文章或許博客評論辯論此話題。
二分查找完成，須要留意的成績
本文禁絕備具體引見一個准確的二分查找應當是若何完成的，究竟如今網上有著年夜量的准確版本。接上去，依據修改試卷進程中發明的一些成績，做一些簡略的剖析，願望對年夜家完成一個有用的二分查找算法，乃至是一個數據庫內可用的二分查找算法，有所贊助。
成績一：能否檢討參數的有用性
年夜量的試卷，在給出此成績的處理算法時，直接拿著low，high參數開端停止盤算，然則卻沒有檢討low/high參數。low/high能否雷同，數組中能否存在記載？low/high組成的區間能否有用？代碼的魯棒性缺乏。
在數據庫的二分查找完成中，普通是對一個索引頁面停止二分查找。索引頁面中有能夠基本不存在用戶的記載(索引頁面中的記載全體被刪除，又沒有與兄弟頁面歸並時)，此時，low/high均為0，此時假如依據low/high盤算出來的mid停止記載的讀取，就存在邏輯毛病。
成績二：二分查找中值的盤算
這是一個經典的話題，若何盤算二分查找中的中值？試卷中，年夜家普通給出了兩種盤算辦法：
算法一： mid = (low + high) / 2
算法二： mid = low + (high – low)/2
乍看起來，算法一簡練，算法二提取以後，跟算法一沒有甚麼差別。然則現實上，差別是存在的。算法一的做法，在極端情形下，(low + high)存在著溢出的風險，進而獲得毛病的mid成果，招致法式毛病。而算法二可以或許包管盤算出來的mid，必定年夜於low，小於high，不存在溢出的成績。
回到數據庫二分查找，數據庫的一個索引頁面(年夜小普通是8k或許是16k)，可以或許存儲的索引記載是無限的，是以確定不會湧現(low + high)溢出的風險。這也是為何InnoDB中的中值，采取的就是算法一的完成。然則，作為一個嚴謹的法式設計人員，照樣推舉應用算法二，將任何潛伏的風險，抹殺於搖籃當中。
成績三：遞歸完成二分查找
跨越一半的試卷，應用了遞歸挪用的方法完成二分查找。不克不及說遞歸完成有錯，而是在於完成效力成績。總所周知，遞歸挪用存在著壓棧/出棧的開支，其效力是比擬低下的。而以數據庫如許一個極端優化代碼效力，供給疾速查詢呼應的體系來講，效力是第一名的。不建議應用遞歸方法完成二分查找，至多在數據庫內核完成中是不許可應用的。據我所知，一切的開源數據庫體系，例如：InnoDB，PostgreSQL都未采取遞歸方法完成二分查找。
成績四：若何查找第一個/最初一個等值
回到標題，請求依據傳入的參數分歧，前往第一個/最初一個等值項。在本文的配景部門，我也說明了此成績對應的數據庫查詢(>，>=查詢需求是分歧的)。在試卷中，跨越80%的同窗的謎底都是先輩行二分查找，待定位到雷同值以後，再依據傳入的flag(用戶需求：flag = 1，前往第一個等值項；flag = 0，前往最初一個等值項)，停止次序遍歷，直至定位到知足前提的項。
異樣，不克不及說這個完成是錯的，然則也存在著機能成績。機能機能機能，永久是數據庫內核完成斟酌的重點之一(信任也是一切運用法式的一個目標)。數據庫中，除主鍵索引/Unique索引可以或許包管鍵值獨一以外，許多二級幫助索引都是存在雷同鍵值的，有時雷同鍵值的項會跨越千項(斟酌一個用戶的定單，或許是購置記載)。
假定一個索引頁面，保留著400項記載，均為雷同鍵值。此時，應用先二分查找，後次序遍歷的算法，二分查找只能應用一次，次序遍歷199次，終究比較了200次。效力異常之低。固然，我也欣喜的看到別的一小部門同窗的做法(我等待看到的算法)，用flag來改正每次比擬的終究成果。例如：比擬相等(相等用0表現，年夜於為1，小於為-1)，然則flag = 1，則前往改正後的比擬成果為1，須要挪動二分查找的high到mid，持續二分(反之，若flag = 0，則前往改正後的成果為-1，須要挪動二分查找的low到mid，持續二分)。如斯一來，等值仍然可以停止二分查找，終究的比較只須要9次，遠遠小於200次。
此成績，進一步引出了下一個成績，數據庫中若何完成一個通用的，更加龐雜的二分查找算法？
成績五：數據庫中的二分查找完成舉例
數據庫中的二分查找，更加龐雜，須要完成一個通用型的二分查找算法，應用於各類分歧的SQL查詢場景。
InnoDB針對分歧的SQL語句，總結出四種分歧的Search Mode，分離為：
#define PAGE_CUR_G 1 >查詢
#define PAGE_CUR_GE 2 >=，=查詢
#define PAGE_CUR_L 3 <查詢
#define PAGE_CUR_LE 4 <=查詢
然後依據這四種分歧的Search Mode，在二分查找碰著雷同鍵值時停止調劑。例如：若Search Mode為PAGE_CUR_G或許是PAGE_CUR_LE，則挪動low至mid，持續停止二分查找；若Search Mode為PAGE_CUR_GE或許是PAGE_CUR_L，則挪動high至mid，持續停止二分查找。
我們的TNT引擎，采取了與InnoDB分歧的計劃，然則也完成了雷同的功效。TNT引擎針對雷同鍵值的調劑總結為下圖，在此我就不做說明了，年夜家可以測驗考試著本身停止剖析。
/* 操作符 includeKey forward compare result: 1 0 -1 */
=============================================================================
>= 1 1 | 1 -1 -1
= 1 1 | 1 -1 -1
> 0 1 | 1 1 -1
< 0 0 | 1 -1 -1
<= 1 0 | 1 1 -1
=============================================================================
