提问者:小点点

如何在swift中调用我的二进制搜索函数?


我是一个老C程序员。我正在尝试用Swift实现一些代码,并且需要一个二进制搜索算法,如果没有完全匹配,它将返回最接近的元素。

我搜索了一下,要么代码一次调用了太多Swift概念,以至于对我的C眼睛来说是不透明的,要么它不适合我的用例。

我决定移植一些旧的C代码来完成工作,并编写了以下内容:

public func bsearch(arr:[Any], target:Double, bcompare:(Any,Double)->Int)-> Int{
    // v is array being searched
    // target is what we're looking for
    // bcompare is a pointer to user-supplied comparison function
    //   bcompare returns -1 if left element < right element, 0 if =, 1 if >
    // target must be same type as v element being compared
   
    // returns index of array element that is closest to <= target
    // note! indexed returned may not match target value
    
    var lo, hi, mid:Int
   
    hi = v.count-1
    if hi <= 0 {return -1}

    lo = 0
    while ((hi-lo) > 1) {
        mid = (hi+lo)/2
        if( bcompare(v[mid], target) == -1){
            lo = mid + 1
        }
        else{
            hi = mid
        }
    }
    if bcompare(v[hi],target) == 0{
        return hi
    }
    return lo
    
}
func eleCompare(left:locArrayele,right:Double)->Int{
    if right < left.degrees{
        return -1
    }
    else if right == left.degrees{
        return 0
    }
    else {
        return 1
    }
}

在C中,您可以将搜索函数指针传递给结构,并告诉编译器如何解释您也传递给搜索函数的比较函数中的内存块。比较函数引用只是另一个内存指针,不需要参数。

我假设Swift“任何”声明相当于指针引用,并在编写上述代码时考虑到了这一想法。编译器抱怨当比较函数将目标称为双精度时将搜索目标声明为任何。为了满足编译器,我将目标声明为双精度,代码编译良好。

我现在的问题是实际测试代码。无论我如何尝试调用搜索函数,编译器都不满意。这个测试片段是我能让编译器满意的最接近的。

       class locArrayele{
            public var degrees  = CLLocationDegrees()       
            public var ix = Int()
            init( degrees:CLLocationDegrees, i:Int){
                self.degrees = degrees
                self.ix = i
            }
        }
       public var latArray : [locArrayele] = [] 
       .
       .
       .
       ix = bsearch(v: latArray, target:35.0, bcompare: eleCompare )
       print(" when lat is 35, closest ix is \(ix))

显然,编译器希望我向eleCompare提供参数,这是我希望bsearch在执行时执行的任务。

我如何调用代码?我意识到我在使用Swift,但我只是想让一些东西工作。优雅可以在我对语言感到舒适的时候出现。


共1个答案

匿名用户

您需要使您的bsearch()通用。您有两种类型可以改变:第一种类型是数组v包含的类型,另一种是目标的类型。

将您的第一行更改为:

public func bsearch<T, U>(v: [T], target: U, bcompare: (T, U) -> Int) -> Int {

调用时不必使用2种不同的类型,但可以。

此示例有一个[String]类型的单词数组,它正在搜索具有5个字母的单词,因此Int中的目标。

let words = ["a", "to", "the", "seven", "butter"]

func compareNameLength(left: String, right: Int) -> Int {
    if left.count < right {
       return -1
    } else if left.count == right {
       return 0
   } else {
       return 1
   }
}

// search for the 5 letter word
let i = bsearch(v: words, target: 5, bcompare: compareNameLength)
print(words[i])
seven

此示例有一个包含素数的[Int],它正在搜索最接近数字的素数而不进行遍历,因此目标是Int

let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

func compareInt(left: Int, right: Int) -> Int {
    if left < right {
        return -1
    } else if left == right {
        return 0
    } else {
        return 1
    }
}

// search for closest prime to 8
let p = bsearch(v: primes, target: 8, bcompare: compareInt)
print(primes[p])
7