二分

概念

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求
线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
例如在一个有序序列中查找某一元素出现的位置,求某单调(或在给定区间上单调)函数的零点。

二分中非常典型的应用就是最小化最大值问题和最大化最小值问题。

模板

二分查找的递归形式

array: 数组
target: 目标元素
# 表示元素可能出现的最小的(最左端)的情况。
left = 0
# 表示元素可能出现的最大的(最有端)的情况。
right = len(array)
def BinarySearch(left, right, array, target):
    if left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            return True
        elif array[mid] < target:
            BinarySearch(mid + 1, right, array, target)  
        else:
            BinarySearch(left, mid + 1, array, target)

二分查找的非递归形式

array: 数组
target: 目标元素
# 表示元素可能出现的最小的(最左端)的情况。
left = 0
# 表示元素可能出现的最大的(最有端)的情况。
right = len(array)
while(left <= right):
    mid = (left + right) // 2
    if array[mid] == target:
        return True
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

二分查找区间

[left, righ]
while left <= right:
    mid = (left + right) // 2
    if array[mid] == target:
        return True
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

(left, right)
while right - left > 1:
    mid = (left + right) // 2
    if array[mid] == target:
        return True
    elif array[mid] < target:
        left = mid
    else:
        right = mid


[left, right)
while left < right:
    mid = (left + right) // 2
    if array[mid] == target:
        return True
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid

应用

最小值最大化问题

通过二分查找得到最大的最小值。

例如:求多个点集的最大的最小距离,即最小差值最大问题。关键在于利用二分查找得到解集中满足条件的最大的最小值。

即获得满足题意的范围解 – 二分缩小范围 – 获得满足题意的范围解 – 二分缩小范围 – · · · – 获得最终解(最大的最小值)

例子

POJ 2456 Aggressive cows

发表评论

电子邮件地址不会被公开。 必填项已用*标注