二分查找有幾種寫法？它們的區(qū)別是什么?

一、二分查找有幾種寫法

二分查找是一種常見的查找算法，它適用于已排序的數(shù)組或列表中查找指定元素的位置。在實(shí)際應(yīng)用中，二分查找有多種實(shí)現(xiàn)方式，以下是比較四種常見的寫法：

1、遞歸寫法

遞歸寫法是一種常見的實(shí)現(xiàn)方式，它將查找過(guò)程遞歸地分成左右兩個(gè)部分，并不斷縮小查找范圍，直到找到目標(biāo)元素或者查找范圍為空。遞歸寫法的實(shí)現(xiàn)代碼較為簡(jiǎn)單，但是需要注意遞歸終止條件和遞歸過(guò)程中參數(shù)的傳遞方式。

2、非遞歸寫法

非遞歸寫法使用循環(huán)來(lái)實(shí)現(xiàn)查找過(guò)程，它通過(guò)不斷縮小查找范圍并更新查找的區(qū)間來(lái)進(jìn)行查找，直到找到目標(biāo)元素或者查找范圍為空。非遞歸寫法的實(shí)現(xiàn)代碼較為復(fù)雜，但是效率較高，不會(huì)出現(xiàn)棧溢出等問(wèn)題。

3、左閉右閉寫法

左閉右閉寫法是一種常見的實(shí)現(xiàn)方式，它將查找區(qū)間定義為左閉右閉區(qū)間，即包含左右兩端點(diǎn)。這種寫法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，易于理解和使用。

4、左閉右開寫法

左閉右開寫法將查找區(qū)間定義為左閉右開區(qū)間，即包含左端點(diǎn)但不包含右端點(diǎn)。這種寫法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，查找區(qū)間更為直觀，但是需要注意邊界條件的處理。

二、二分查找寫法之間的區(qū)別

以上四種實(shí)現(xiàn)方式之間的區(qū)別主要體現(xiàn)在以下幾個(gè)方面：

1、實(shí)現(xiàn)方式不同

遞歸寫法和非遞歸寫法的實(shí)現(xiàn)方式不同，遞歸寫法使用遞歸來(lái)實(shí)現(xiàn)查找過(guò)程，非遞歸寫法使用循環(huán)來(lái)實(shí)現(xiàn)查找過(guò)程。

2、實(shí)現(xiàn)復(fù)雜度不同

遞歸寫法的實(shí)現(xiàn)代碼較為簡(jiǎn)單，但是需要注意遞歸終止條件和遞歸過(guò)程中參數(shù)的傳遞方式。非遞歸寫法的實(shí)現(xiàn)代碼較為復(fù)雜，但是效率較高，不會(huì)出現(xiàn)棧溢出等問(wèn)題。

3、區(qū)間定義不同

左閉右閉寫法和左閉右開寫法的區(qū)間定義不同，左閉右閉區(qū)間包含左右兩端點(diǎn)，左閉右開區(qū)間包含左端點(diǎn)但不包含右端點(diǎn)。

4、邊界處理不同

左閉右閉寫法和左閉右開寫法的邊界處理不同，左閉右閉寫法的邊界處理比較簡(jiǎn)單，但是在處理邊界時(shí)需要注意左右端點(diǎn)的順序。左閉右開寫法的邊界處理比較復(fù)雜，需要特別注意右端點(diǎn)的邊界條件。

在實(shí)際應(yīng)用中，應(yīng)該根據(jù)具體需求和場(chǎng)景選擇合適的實(shí)現(xiàn)方式。如果數(shù)據(jù)量較小，遞歸寫法和左閉右閉寫法是比較合適的選擇；如果數(shù)據(jù)量較大，非遞歸寫法和左閉右開寫法效率更高。同時(shí)，不同實(shí)現(xiàn)方式之間也可以相互結(jié)合，比如可以使用非遞歸寫法和左閉右閉寫法結(jié)合，以兼顧效率和實(shí)現(xiàn)簡(jiǎn)單性。

延伸閱讀1：二分查找的查找長(zhǎng)度怎么算

二分查找的查找長(zhǎng)度指的是二分查找算法在查找過(guò)程中，需要查找的元素個(gè)數(shù)。一般來(lái)說(shuō)，我們可以通過(guò)查找區(qū)間的長(zhǎng)度來(lái)計(jì)算二分查找的查找長(zhǎng)度。在二分查找的過(guò)程中，每次都將查找區(qū)間分為兩個(gè)部分，如果目標(biāo)元素在左邊的區(qū)間，則繼續(xù)在左邊的區(qū)間進(jìn)行查找，否則在右邊的區(qū)間進(jìn)行查找，以此類推。因此，每次查找后，查找區(qū)間的長(zhǎng)度都會(huì)縮小為原來(lái)的一半。

假設(shè)初始的查找區(qū)間長(zhǎng)度為n，則名列前茅次查找后，查找區(qū)間的長(zhǎng)度縮小為n/2；第二次查找后，查找區(qū)間的長(zhǎng)度縮小為n/4；第三次查找后，查找區(qū)間的長(zhǎng)度縮小為n/8，以此類推。因此，可以通過(guò)不斷將查找區(qū)間長(zhǎng)度除以2，來(lái)計(jì)算二分查找的查找長(zhǎng)度。

具體而言，如果二分查找的查找區(qū)間長(zhǎng)度為n，則二分查找的查找長(zhǎng)度為log?n。這是因?yàn)?，每次查找后，查找區(qū)間的長(zhǎng)度都會(huì)縮小為原來(lái)的一半，因此查找次數(shù)非常多為log?n次。

需要注意的是，在實(shí)際應(yīng)用中，二分查找的查找長(zhǎng)度可能會(huì)受到多種因素的影響，比如查找元素的位置、查找區(qū)間的大小、算法的實(shí)現(xiàn)方式等等，因此需要根據(jù)具體情況進(jìn)行分析和計(jì)算。