【案例內(nèi)容】

N個有序整數(shù)數(shù)列已放在一位數(shù)組中，利用二分查找法查找整數(shù)m在數(shù)組中的位置。若找到，則輸出其下標(biāo)值；反之，則輸出“無此數(shù)字”。

【解題思路】

二分查找法，也叫折半查找。其本質(zhì)是分治算法的一種，所謂分治算法就是分而治之，即將較大規(guī)模的問題分解成幾個較小規(guī)模的問題，而這些較小的問題相互獨(dú)立，并且與原問題的解法類似，通過對較小問題的求解，以達(dá)到對整個問題的求解。舉例來說，比如在一個有序排列的整數(shù)列表中，先取得正中間（或接近正中間）一個整數(shù)的索引（假設(shè)為：middle），比較要查找的數(shù)字（假設(shè)為：num），與該索引所對應(yīng)的數(shù)值（假設(shè)為：nums[middle]）的大小，如果num > nums[middle]，那么索引就從 middle+1 到結(jié)尾（假設(shè)為：end）繼續(xù)查找；如果num < nums[middle]，那么索引就從開頭（假設(shè)是：start）到?middle-1 繼續(xù)查找。如此循環(huán)反復(fù)的一直找下去，終究會找到當(dāng) num == nums[middle]，則此時返回索引值 middle，那么該索引就是所要查找的數(shù)字 num 的下標(biāo)值。當(dāng)然一開始要先判斷 num 是否在 列表 nums 中，可以直接用 if num in nums 來判斷，也可以接著上面的二分查法，直到 start == end 的時候還沒查到，則按題意，輸出“無此數(shù)字”即可。

【Python代碼】

二分查找法，每次都把數(shù)列折半查找，因此查找的數(shù)量都減半，對數(shù)據(jù)量很大的數(shù)列，效率較高。本題中沒有出現(xiàn)重復(fù)的數(shù)字，請讀者朋友們自行嘗試出現(xiàn)相同數(shù)字的情況。