Python二分法查找及变种分析

时间:2022-10-28 10:38:15

基于Python3

普通二分法查找目标值的index

二分法查找的思路很简单,先确定好列表nums的一头start一尾end,中间值middle根据头尾数值之和用地板除法除以2,即(start + end) // 2。将目标值target与nums[middle]进行比对,这时候有3种结果:

  1. nums[middle] > target
  2. nums[middle] < target
  3. nums[middle] = target

以上3种情况前2种不断循环,直到满足第3种跳出循环。

情况1

说明target在前半段,所以end=middle-1

情况2

说明target在后半段,所以start=middle+1

情况3

说明target就是nums[middle],所以返回middle,这是跳出循环的方式之一

所以到此可以写出循环体中的代码,如下:

       middle = (start + end) // 2
if target > nums[middle]:
start = middle + 1
elif target < nums[middle]:
end = middle - 1
else:
return middle

但是,万一一直达不到第3种的条件呢?即target压根不在列表nums中,这就出现了情况4

情况4

我们循环到最后阶段一定是start=middle-1=end-2,即start与middle与end紧挨着。这时候,我们将start,middle,end代入if语句进行分析,

  1. nums[middle] > target,所以赋值end=middle-1,这时end且又和start相等
  2. nums[middle] < target,所以赋值start=middle+1,这时start且又和end相等

那么此时还有最后一个值需要判断,以上2种情况再代入循环体,此时有start=end=middle。若没有nums[middle]=target,则跳出循环(此为跳出循环的方式之二)返回-1

很明显,start与end一直互相逼近,但是start一直小于end的,要不要加上等于这个条件呢?别忘了只有start=end,才能够对列表中的最后一个元素进行判断。

完整代码如下:

def binarySearch(nums, target):
start = 0
end = len(nums) -1
while start <= end:
middle = (start + end) // 2
if target > nums[middle]:
start = middle + 1
elif target < nums[middle]:
end = middle - 1
else:
return middle
return -1 if __name__ == "__main__":
List = [1,4,4,5,7,7,8,9,9,10]
print(List)
print(binarySearch(List, 1)) # output
# [1, 4, 4, 5, 7, 7, 8, 9, 9, 10]
# 0

变种二分法查找

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。

普通的二分查找只要找到target就行了,这个必须考虑到列表中重复的元素。

也就是说,即便找到了也不能跳出循环体。那么怎样才能跳出循环体呢?

别忘了跳出循环的方式有2种,刚才只是封住了第1种,还有第2种呢。即while的设置条件。很明显,start小于end是必须的循环条件的,而start大于end肯定是跳出循环的条件,那么start=end是跳出还是不跳出呢?首先要清楚start=end的意义是什么,即经过迭代此时列表nums中的选择区域变成了一个元素,循环的作用是将这最后一个元素选出来。

跳出循环,去判断是哪种可能。这个元素只有2种可能:不满足target或者是满足target的第一个元素。

可能一:不满足target的过程

注意,和普通二分法情况一样,循环到最后阶段一定是start=middle-1=end-2,即start与middle与end紧挨着。这时候,我们将start,middle,end代入if语句进行分析,

  1. nums[middle] > target,所以赋值end=middle-1,这时end且又和start相等
  2. nums[middle] < target,所以赋值start=middle+1,这时start且又和end相等

    此时start=end,跳出循环,判断不满足target,需要return -1

可能二:满足target的第一个元素的过程

如何确定是满足target的第一个元素?

先明白循环中找到第一个等于target的nums[middle]元素不跳出循环应该做什么。很明显,应该搜寻nums[start:middle]区域,所以要赋值end=middle,即搜寻新的nums[start:end]区域。再次循环,此时只剩下2种结果,再找到等于target的nums[middle] 或者 找不到了

结果1再找到等于target的nums[middle]

  • 第一步得到middle = (start + end) // 2
  • 有target = nums[middle]
  • 赋值end=middle
  • 进入新的循环,搜寻新的nums[start:end]区域,依然面临2种结果

结果2再找不到等于target的nums[middle]

  • 第一步得到middle = (start + end) // 2
  • 一定有nums[middle] < target而不是nums[middle] > target,因为nums是递增的。
  • 此时start = middle + 1
  • 进入新的循环,搜寻新的nums[start:end]区域,依然面临2种结果

以上2种结果互相交错,循环到最后阶段一定是start=middle-1=end-2,即start与middle与end紧挨着。这时候,我们将start,middle,end代入if语句进行分析,

  1. nums[middle] < target,所以赋值start=middle+1,这时start且又和end相等,此时start=end,跳出循环,判断nums[start] == target,需要return start。
  2. nums[middle] = target,所以赋值end=middle,得到start=middle-1,再带入循环,有middle = (start + end) // 2,得到start=middle=end-1。

    此时最后一步又分为二,1若nums[middle] < target,所以赋值start=middle+1,这时start且又和end相等,此时start=end,跳出循环,判断nums[start] == target,需要return start。2若nums[middle] = target,所以赋值end=middle,得到start=middle=end,跳出循环,判断nums[start] == target,需要return start。
def binarySearch(nums, target):
start = 0
end = len(nums) -1
while start < end:
middle = (start + end) // 2
if target > nums[middle]:
start = middle + 1
elif target < nums[middle]:
end = middle - 1
else:
end = middle
if nums[start] == target:
return start
return -1 if __name__ == "__main__":
List = [1,4,4,5,7,7,8,9,9,10]
print(List)
print(binarySearch(List, 4)) # output
# [1, 4, 4, 5, 7, 7, 8, 9, 9, 10]
# 1