Python迭代式二分查找实现：输入校验、复杂度及优化问询

我已经用Python实现了迭代式二分查找，现在有以下几个问题：

1. 如何高效确保输入数组已排序，若未排序则进行排序？
2. 怎样验证输入数组是否有序？
3. 输入未排序时的时间复杂度是多少？
4. 希望得到该代码的效率优化建议。

原实现代码 #

def binary_search(array, search):
    low = 0
    high = len(array)

    while low <= high and len(array[low:high]):
        mid = (low + high) // 2
        if array[mid] == search:
            return "Found " + str(search) + " at index " + str(mid)
        elif search > array[mid]:
            low = mid + 1
        elif search < array[mid]:
            high = mid - 1

    return str(search) + " not found."


search_through = [2, 3, 4, 10, 40]
to_search = 49
print(binary_search(search_through, to_search))

原输出 #

49 not found.

一、验证数组是否有序 #

通过遍历数组，检查相邻元素的顺序即可（以升序为例，二分查找默认依赖升序数组），时间复杂度为O(n)：

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i+1]:
            return False
    return True

如果需要验证降序，将判断条件改为arr[i] < arr[i+1]即可。

二、确保输入数组已排序（未排序则排序） #

先调用上述is_sorted函数判断数组状态，若未排序则使用Python内置的sorted()函数（基于Timsort算法，时间复杂度O(n log n)）进行排序。如果允许修改原数组，也可以用原地排序的arr.sort()。

示例处理逻辑：

def ensure_sorted(arr):
    if not is_sorted(arr):
        return sorted(arr)
    return arr.copy()  # 返回副本避免修改原数组，无需保留原数组可直接return arr

注意：排序会改变原数组的索引，如果需要保留原索引信息，可以将数组元素转为(值, 原索引)的元组后再排序。

三、输入未排序时的时间复杂度 #

如果先排序再执行二分查找，总时间复杂度由排序的O(n log n)主导，加上二分查找的O(log n)，最终时间复杂度为O(n log n)。
如果不排序直接执行二分查找，算法逻辑会失效（可能找不到存在的元素或返回错误索引），此时讨论时间复杂度没有实际意义。

四、代码效率优化建议 #

1. 修复索引越界bug：原代码中high = len(array)会导致循环后期访问array[mid]时出现索引越界，应改为high = len(array) - 1。
2. 移除冗余循环条件：len(array[low:high])会生成切片，额外消耗内存和时间，low <= high已经能保证区间有效，直接删除该条件。
3. 优化mid计算：将mid = (low + high) // 2改为mid = low + (high - low) // 2，避免整数溢出风险（Python无溢出问题，但写法更通用）。
4. 返回原始索引而非字符串：原函数返回格式化字符串不利于后续逻辑处理，建议返回找到的索引，未找到则返回-1或None，由调用方处理输出。
5. 增加空数组判断：提前判断输入数组是否为空，避免进入循环后报错。
6. 添加类型提示：提升代码可读性和可维护性。

优化后的代码 #

def binary_search(array: list[int], search: int) -> int:
    if not array:
        return -1
    
    low = 0
    high = len(array) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        if array[mid] == search:
            return mid
        elif search > array[mid]:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

# 使用示例
search_through = [2, 3, 4, 10, 40]
to_search = 49
result = binary_search(search_through, to_search)
print(f"Found {to_search} at index {result}" if result != -1 else f"{to_search} not found.")

内容的提问来源于stack exchange，提问作者Faisal Khan