Python编程算法【九】 折半查找

【案例内容】

N个有序整数数列已放在一位数组中，利用二分查找法查找整数m在数组中的位置。若找到，则输出其下标值；反之，则输出“无此数字”。

【解题思路】

二分查找法，也叫折半查找。其本质是分治算法的一种，所谓分治算法就是分而治之，即将较大规模的问题分解成几个较小规模的问题，而这些较小的问题相互独立，并且与原问题的解法类似，通过对较小问题的求解，以达到对整个问题的求解。举例来说，比如在一个有序排列的整数列表中，先取得正中间（或接近正中间）一个整数的索引（假设为：middle），比较要查找的数字（假设为：num），与该索引所对应的数值（假设为：nums[middle]）的大小，如果num > nums[middle]，那么索引就从 middle+1 到结尾（假设为：end）继续查找；如果num < nums[middle]，那么索引就从开头（假设是：start）到 middle-1 继续查找。如此循环反复的一直找下去，终究会找到当 num == nums[middle]，则此时返回索引值 middle，那么该索引就是所要查找的数字 num 的下标值。当然一开始要先判断 num 是否在 列表 nums 中，可以直接用 if num in nums 来判断，也可以接着上面的二分查法，直到 start == end 的时候还没查到，则按题意，输出“无此数字”即可。

【Python代码】

二分查找法，每次都把数列折半查找，因此查找的数量都减半，对数据量很大的数列，效率较高。本题中没有出现重复的数字，请读者朋友们自行尝试出现相同数字的情况。