Python编程题51--二分查找

题目

给定一个含有 n 个无重复整数的升序列表 nums 和一个目标值 target ，请查找 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

例如：

给定一个列表 nums ：[-1, 0, 3, 5, 9, 12]，target = 9
返回结果：4

给定一个列表 nums ：[-1, 0, 3, 5, 9, 12]，target = 2
返回结果：-1

实现思路

在本题中说明了 nums 是一个有序列表，并且列表中元素无重复，因此我们可以考虑使用 二分查找 来实现。

• 定义2个变量：left、right ，分别表示左边界下标和右边界下标，left 默认值为第一个元素下标，即 left = 0，right 默认值为最后一个元素下标，即 right = len(nums) - 1
• 首先，计算出 left 和 right 之间的中间元素下标 mid = (left + right) // 2，并将中间元素 nums[mid] 与目标值 target 进行比较，总共分为3种情况
• 第一种情况，如果中间元素等于 target ，那么直接返回 mid 即可
• 第二种情况，如果中间元素大于 target ，那么说明 target 出现在中间元素的左侧，所以需要修改右边界下标 right = mid - 1
• 第三种情况，如果中间元素小于 target ，那么说明 target 出现在中间元素的右侧，所以需要修改左边界下标 left = mid + 1
• 当 left 小于等于 right ，我们就对以上几步进行重复操作，如果在列表中查找到 target ，那么就可以直接返回对应下标，如果最后 left 大于 right 时还没有查找到 target ，那么就说明列表中不存在 target ，停止循环并返回 -1

我们可以发现，二分查找的逻辑其实不难，但它在实现过程中，涉及到不少边界条件，很容易弄乱，因此我们在实现过程中必须对变量的区间考虑清楚。

代码实现--while循环，非递归

class Solution:
    def binary_search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

代码实现--递归

class Solution:
    def binary_search(self, nums, target):
        return self.binary_search_recursive(nums, target, 0, len(nums) - 1)

    def binary_search_recursive(self, nums, target, left, right):
        if left > right:
            return -1
        mid = (left + right) // 2
        if nums[mid] > target:
            return self.binary_search_recursive(nums, target, left, mid - 1)
        elif nums[mid] < target:
            return self.binary_search_recursive(nums, target, mid + 1, right)
        else:
            return mid

更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）