LeetCode in Python 704. Binary Search (二分查找)
二分查找是一种高效的查询方法，时间复杂度为O(nlogn)，本文给出二分查找的代码实现。
示例：
代码：
class Solution:
def search(self, nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] > target:
r = mid - 1
elif nums[mid] < target:
l = mid + 1
else:
return mid
return -1 解释：
1）当nums[mid] > target时表明target在[0, mid]区间内，故将右指针r移至mid-1，同理当nums[mid] < target时表明target在[mid, len(nums) - 1]区间内，将左指针移至mid+1，直到不满足循环l<=r时退出或找到target的位置返回下标指针。
2）注意while循环的条件l<=r，若为l<r，则当数组只有一个元素时将无法返回正确下标位置。
原文地址：https://blog.csdn.net/m0_45175452/article/details/137913812
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！