Python实现二分查找_python二分查找

1. 什么是二分查找？

给定以下情景，假设有一个有序的数组（从大到小排列），我们需要从中找出我们所需的目标元素并返回其索引。一般的思想是可以使用for循环进行遍历，直到找到目标元素然后返回其索引。但是这种方法的效率是十分低下的，如果我们的目标元素在最后一个，而我们的数组又十分长时，检索是十分耗时的。

此时不妨通过二分查找来提高我们的检索效率。首先来说，若使用二分查找，必须满足一个首要条件，便是目标元素所在的数组必须是有序的。至于为什么要使用有序数组等看完代码在讲述。

2. 二分查找的思路

假设我们目标元素所在的数组为nums，目标元素为target，首先我们要定义两个变量i = 0和j = len(nums) - 1，这里的两个元素分别是nums第一个元素和最后一个元素的索引。

然后我们使用一个while循环来查找我们的目标元素，而跳出while循环的条件是i <= j。然后我们定义m = (i + j) // 2，这里的m是nums中间元素的索引。

然后我们将nums[m]与target进行比较，若target > nums[m]，则表明target在nums[m]的右边，这时我们将i = m + 1，然后重新求得新的m。若target < nums[m]，则表明target在nums[m]左边，这是我们将j= m - 1，然后在重新求得我们的m。以此类推，直到我们找到了我们的target，即target == nums[m]，此时跳出循环，并返回m，即target的索引。又或者此时已经不满足i <= j的条件，即i > j了，我们也跳出while循环，返回-1，表明未找到target。

解读：为什么i <= j作为跳出while循环的条件时要存在=？

• 假设我们的target所在位置正好是最后一个元素，即nums[j]，随着while的不断执行，我们的m和i也会不断的增加，假设此时i = 4, j = 5，通过计算可知m = 4。此时的nums[m]依然小于target，然后i = m + 1 = 5，若while循环条件为i < j，则跳出循环，返回了-1，查找失败。若while循环条件为i <= j，则继续执行m = (i + j) // 2 = (5 + 5) // 2 = 5，num[5]即我们所需要的target，跳出循环，返回m = 5。

3. 代码实现

非递归实现

def binary_search(self, nums, target):
    i = 0
    j = len(nums) - 1
    m = -1
    while i <= j:
        m = (i + j) // 2
        if target == nums[m]:
            return m
        elif target > nums[m]:
            i = m + 1
        else:
            j = m - 1
1
2
3
4
5
6
7
8
9
10
11
12

递归实现

def binary_search_recursive(self, nums, target, start, end):

    while start <= end:
        m = (start + end) // 2
        if target == nums[m]:
            return m
        elif target > nums[m]:
            return self.binary_search_recursive(nums, target, start + 1, end)
        else:
            return self.binary_search_recursive(nums, target, start, end + 1)
1
2
3
4
5
6
7
8
9
10

至于为何nums必须为有序数组，若nums为无序数组，在一次求得完m之后便无法继续确认target是在nums[m]的左半区还是右半区了，因为每个半区都会有大于和小于nums[m]的数字，因此无序数组是没有意义的。