二分查找及python实现
程序员文章站
2022-03-14 20:43:51
...
二分查找适合对于有序表的查找
每次通过与区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0
时间复杂度就是O(logn)
// 表示整数除法,返回一个不大于" / "计算结果的最大整数int(即为下取整)
def binarySearch(nums, target):
if len(nums) == 0:
return False
else:
length = len(nums)
midpoint = length //2
print(midpoint)
if nums[midpoint] == target:
return True
else:
if target<nums[midpoint]:
return binarySearch(nums[:midpoint],target)
else:
return binarySearch(nums[midpoint+1:],target)
nums=[5,6,7,8,10,23,58,96]
target = 6
print(binarySearch(nums, target))