Python二分查找算法原理与实战代码解析

拾光

发布时间：2026-10-15| 5人浏览过

原创

本文深入解析Python中二分查找算法的核心原理，重点阐述其O(log2n)的时间复杂度优势及仅适用于有序列表的局限性。通过三个典型的LeetCode编程题目，详细展示了升序数组搜索、递减数组查找及两数之和问题的二分法代码实现，帮助开发者掌握该算法在实际场景中的应用。

二分查找算法原理与适用场景

二分查找算法的核心优势在于：随着待搜索元素数量的增加，其速度优势相比简单查找愈发显著。然而，该算法存在明显的局限性，即它仅适用于已经排序的列表。由于二分查找依赖于数据的有序性，这导致在列表中进行插入或删除操作变得非常困难。因此，折半查找方法最适合应用于那些数据相对固定、不经常发生变动的有序列表场景。

二分查找的关键特征在于它无需遍历数列中的所有元素，而是通过不断缩小搜索范围来定位目标。每次查找后，待查数据量大致减半，这种对数级的增长模式使得二分查找的时间复杂度稳定为 O(log2n)。虽然最佳情况下只需一次比较即可找到目标，但在最坏和一般场景下，其效率仍远优于顺序查找。

二分查找经典题目实战

题目一：给定一个包含 n 个元素的升序整型数组 nums 以及一个目标值 target，编写一个函数在 nums 中搜索 target。若目标值存在，则返回其下标；若不存在，则返回 -1。


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

题目二：在一个严格递减的数组中，寻找第二个比目标值 target 大的数的下标。如果找不到满足条件的数，则返回 -1。


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

题目三：函数需以长度为 2 的整数数组形式返回这两个数的下标值。注意 numbers 的下标从 1 开始计数，因此返回的答案数组必须满足 1 <= answer[0] < answer[1] <= numbers.length 的条件。每个输入仅对应唯一的答案，且不可重复使用相同的元素。


class Solution:
     def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)-1):
            left=i
            right=len(numbers) - 1
            while(left<=right):
                mid=(left+right)//2
                if numbers[mid]+numbers[i]==target:
                    return [i+1,mid+1]
                elif numbers[mid]+numbers[i]<target:
                    left=mid+1
                else:
                    right = mid-1
            return [-1,-1]