代码之家 › 专栏 › 技术社区 › stevenpcurtis

实现二进制搜索的Swift可选参数

swift

stevenpcurtis · 技术社区 · 7 年前

我想用Swift编写一个很好的二进制搜索的实现,下面的代码看起来像是一个在所有情况下都要克服传递上下限的技巧。

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: Int? = 0) -> Int? {
    var ub = upperBound
    if (ub == 0 ) { ub = arr.count
}

XCTAssertEqual(binarySearch(arr: [1,2,3,4], target: 5), nil)

首先,我不想把上下界传递给二进制搜索。

我的函数头如下所示:

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: Int? = 0) -> Int? {

在二进制搜索的每个递归调用中,下限要么是零,要么是传递的参数,这是有意义的。但上界不是。

现在我想写一些

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: arr.count) -> Int? {

我甚至想添加以下内容(但显然不能,因为上界是let常量):

if (upperBound == 0 ) {upperBound = arr.count}

我想使用:

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ var upperBound: Int? = 0) -> Int? {

我不得不使用一个额外的变量如下,因为这是一个混乱!

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: Int? = 0) -> Int? {
    var ub = upperBound
    if (ub == 0 ) {ub = arr.count}

2 回复 | 直到 7 年前

rmaddy 7 年前

nil . 然后创建本地 ub

let ub = upperbound ?? arr.count

下限应该是非可选的,默认值为 0 .

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int = 0, _ upperBound: Int? = nil) -> Int? {
    let ub = upperBound ?? arr.count

Alexander 7 年前

这是一种常见的情况。递归函数的签名可能需要比其入口点更多的参数。处理这个问题的最佳方法是使用嵌套函数。

func binarySearch(_ array: [Int], for target: Int) -> Int? {
    func binarySearch(_ array: [Int], for: Int, lowerBound: Int, upperBound: Int) -> Int? {
        // your implementation here
    }

    return binarySearch(array, for: target, lowerBound: 0, upperBound: array.count)
}

要获得更快速的代码,我建议您转换并尝试使用:

一个扩展,而不是一个自由函数,它使用一个参数来表示有效的“self”
一个范围而不是两个独立的 Int
一个具有最小参数的公共入口点和一个私有递归函数将为递归提供所有必需的参数。

extension RandomAccessCollection where Self.IndexDistance == Int {
    public func binarySearch(for target: Element) -> Int? {
        return binarySearch(for: target, inRange: 0 ..< self.count)
    }

    private func binarySearch(for target: Element, inRange range: CountableRange<Int>) -> Int? {
        return nil // Your implementation here
    }
}

推荐文章

sudoExclamationExclamation · iOS自动布局-高度不能小于ThanOrEqualTo

1 年前

Tom · SwiftUI.sheet导致背景白色闪烁

1 年前

Danil · 种子/填充核心数据的最佳实践?[关闭]

1 年前

Z S · SwiftUI:使用@FocusState。与视图初始化器绑定

1 年前

Robin · LazyVGrid项目预计不会击中测试区域

1 年前

Mahendra · Popover不是从SwiftUI中的项目列表中打开的[重复]

1 年前

Saurabh Saini · 结构下标

1 年前

Alex Smith · 移动到下一个视图控制器后如何显示警报?

1 年前

jnwjack · Swift:初始化不安全可变指针<CGImage?>不分配

1 年前

Moses Harding · 在SwiftUI的ForEach中以绑定和非绑定方式使用数组的单个成员,而不使用索引

1 年前