二分查找有几种写法？它们的区别是什么

二分查找，又称折半查找，是一种高效的搜索算法，用于在有序数组中查找特定元素。它的基本原理是通过反复将目标元素与数组中间元素进行比较，将搜索范围对半分，从而快速缩小目标元素的可能范围。

二分查找有多种实现方式，每种写法都有其独特的优点和适用场景。下面，我将介绍三种常见的二分查找写法：

1. 循环版二分查找

这是最基本的二分查找实现方式，采用循环逐步缩小搜索范围。

“`python
def binarysearchloop(arr, target):
low = 0
high = len(arr) – 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
return -1  # 未找到目标元素

“`

循环版二分查找的优点是实现简单，易于理解和调试。缺点是循环次数相对较多，对于大规模数组的查找效率较低。

2. 递归版二分查找

递归版二分查找采用递归算法，将问题分解为较小的子问题并逐步求解。

“`python
def binarysearchrecursive(arr, target, low, high):
if low > high:
return -1

mid = (low + high) // 2
if arr[mid] == target:
    return mid
elif arr[mid] < target:
    return binary_search_recursive(arr, target, mid + 1, high)
else:
    return binary_search_recursive(arr, target, low, mid - 1)

“`

递归版二分查找的优点是实现简洁，代码量少。缺点是递归调用会消耗栈空间，对于深度较深的递归可能导致栈溢出。

3. 迭代版二分查找

迭代版二分查找结合了循环和递归的优点，在循环中使用栈结构模拟递归调用。

“`python
def binarysearchiterative(arr, target):
stack = []
stack.append((0, len(arr) – 1))

while stack:
    low, high = stack.pop()
    if low > high:
        continue
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        stack.append((mid + 1, high))
    else:
        stack.append((low, mid - 1))
return -1  # 未找到目标元素

“`

迭代版二分查找的优点是结合了循环和递归的优点，既能节省栈空间，又能实现简洁的代码。

写法的选择

三种二分查找写法各有优缺点，在不同的场景下有不同的适用性：

• 对于小规模数组或效率要求不高的场景，可以采用循环版二分查找。
• 对于大规模数组或需要简洁代码的场景，可以采用递归版二分查找。
• 对于需要兼顾栈空间和代码简洁性的场景，可以采用迭代版二分查找。

根据具体需求选择合适的写法，可以最大化二分查找的效率和鲁棒性。

在计算机科学领域，二分查找是一种高效的算法，用于在排序数组中查找目标元素。该算法利用数组已排序的特性，通过不断将搜索范围缩小一半，快速找到目标元素或确定其不存在。

1. 递归写法

这是二分查找最经典的写法：


def binary_search_recursive(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return binary_search_recursive(arr, target, low, mid - 1)


该写法使用递归函数，以降低和升序分别向左和向右搜索。它易于理解和实现，但递归调用会导致额外的空间开销。

2. 非递归写法（循环写法）

为了避免递归带来的开销，我们可以使用非递归写法：


def binary_search_iterative(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1


这个写法采用循环来模拟递归的过程，避免了递归栈的开销。它更适合于需要多次进行二分查找的场景。

3. 数组切片写法

在Python等高级编程语言中，我们可以利用数组切片特性简化二分查找的写法：


def binary_search_pythonslice(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1


在这个写法中，我们使用数组切片 arr[low:high] 来指定搜索范围，每次将搜索范围缩小一半，直到找到目标元素或确定其不存在。

4. 二分查找变体

除了上述基本写法外，二分查找还有多种变体，用于解决不同场景下的问题：

• 插值查找：针对元素分布均匀的数组，通过线性插值估计目标元素的位置。
• 斐波那契查找：利用斐波那契数列，在某些情况下可以比标准二分查找更快。
• 指数查找：当数组元素数量极大时，通过指数增长快速定位目标元素。

写法选择

选择哪种二分查找写法取决于具体应用场景。递归写法适合于理解和实现简单，但对于深度嵌套的递归调用可能导致性能下降。非递归写法避免了递归开销，但可能牺牲代码可读性。数组切片写法简洁高效，但仅适用于支持数组切片的语言。变体写法适用于特定的性能优化需求。

在实际应用中，需要综合考虑数组规模、查找频率、编程语言特性等因素，选择最合适的二分查找写法，以达到最佳性能和代码可维护性。

大家好，今天就来聊聊二分查找这个算法。二分查找是一种及其高效的查找算法，特别适用于有序数组中查找元素。

二分查找算法简介

二分查找算法的基本原理是：将有序数组分为两半，不断缩小查找范围，直到找到目标元素或确定其不存在。

二分查找的写法

二分查找有多种写法，每种写法都有其特点和适用场景。以下是几种常见的写法：

1. 递归写法

python
def binary_search_recursive(arr, target, low, high):
if low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return binary_search_recursive(arr, target, low, mid - 1)
else:
return -1


优点：代码简洁，易于理解。
缺点：当数组规模较大时，递归调用的次数过多，容易造成栈溢出。

2. 迭代写法

python
def binary_search_iterative(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1


优点：避免了栈溢出问题，性能更稳定。
缺点：代码略显冗长，需要手动维护 low 和 high 变量。

3. 哨兵值写法

python
def binary_search_sentinel(arr, target):
arr.append(target) # 添加哨兵值
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
if mid < len(arr) - 1 or arr[mid + 1] != target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1


优点：简化了比较逻辑，避免了特殊情况的判断。
缺点：需要修改原数组，增加了代码复杂度。

4. 标志位写法

python
def binary_search_flag(arr, target):
low, high = 0, len(arr) - 1
found = False
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
found = True
break
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return found


优点：不需要额外存储中间结果，代码简洁。
缺点：无法得到目标元素在数组中的位置，仅能判断是否存在。

选择写法的建议

选择哪种写法取决于具体需求和数组规模：

• 对于小型数组，递归写法更为简洁。
• 对于大型数组，迭代写法更稳定，性能更好。
• 哨兵值写法适用于需要简化判断逻辑的情况。
• 标志位写法仅适用于判断元素是否存在，无需得到其位置。

总之，二分查找是一种高效实用的算法，根据不同的需求和情况，选择合适的写法可以充分发挥其优势。