二分查找(下)

Tuesday, April 23, 2019

上面一节只描述了最简单的一种二分查找问题,就是不存在重复元素的有序数组中,查找值等于给定值的元素。这里就要讲讲二分查找的变形问题。

file

查找第一个值等于给定值的元素

比如我们希望找到第一个等于8的数据,也就是下标5的元素。

file

如果用上一节的代码实现,并不会返回第一个等于8的元素。所以我们需要改进我们的二分法代码。

<code class="language-swift">public func bsearch(_ array:[Int], n: Int, value: Int) -> Int {
    var low = 0
    var high = n - 1

    while low <= high {
        let mid = low + ((high - low) >> 1)
        if a[mid] > value {
            high = mid - 1
        }else if a[mid] < value {
            low = mid + 1
        }else {
            if mid == 0 || a[mid - 1] != value {
                return mid
            }else {
                high = mid - 1
            }
        }
    }
    return -1
}</code>

查找最后一个值

与上述类似,只是将判断条件稍微修改即可

<code class="language-swift">public func besearch(_ array: [Int], n: Int, value: Int) -> Int {
    var low = 0
    var high = n - 1
    while low <= high {
        let middle = low + ((high - low) >> 1)
        if a[middle] > value {
            high = middle - 1
        }else if a[middle] < value {
            low = middle + 1
        }else {
            if middle == n - 1 || a[middle + 1] != value {
                return middle
            }else {
                low = middle + 1
            }
        }
    }
    return -1
}</code>

查找第一个大于等于给定值的元素

<code class="language-swift">public func besearch(_ array: [Int], n: Int, value: Int) -> Int {
    var low = 0
    var high = n - 1
    while low <= high {
        let middle = low + ((high - low) >> 1)
        if a[middle] < value {
            low = middle + 1
        }else if a[middle] >= vlaue {
            if middle == 0 || a[middle - 1] < value {
                return middle
            }else {
                high = middle - 1
            }
        }else {
            low = middle + 1
        }
    }
    return -1
}</code>

查找最后一个小于等于给定值的元素

与上面类似,不再阐述

数据结构-算法

散列表(上)

二分查找(上)