二分查找:传递数组时出错 [英] Binary search: error in passing array

问题描述

我有一个名为 array 的对象数组，它的类型是 votes.在数组的对象中有一个名为 nameSubject 的字段，它是一个字符串.如何传递我的数组和我想与主题名称进行比较的字符串?这是我的功能:

I have an array of objects called array and its type is votes. In the objects of the array there is a field called nameSubject that is a String. How can I pass my array and the String that I want to compare with the name of the subject? This is my function:

static func binarySearch(inputArr: [votes], searchItem: String)->Int?{
    var lowerIndex = 0;
    var upperIndex = inputArr.count - 1

    while (true) {
        var currentIndex = (lowerIndex + upperIndex)/2
        if(inputArr[currentIndex] == searchItem) {
            return currentIndex
        } else if (lowerIndex > upperIndex) {
            return nil
        } else {
            if (inputArr[currentIndex] > searchItem) {
                upperIndex = currentIndex - 1
            } else {
                lowerIndex = currentIndex + 1
            }
        }
    }
}

错误在第一个和第二个 if 中并说明:二元运算符=="不能应用于投票"和字符串"类型的操作数"

The error is in the first and in the second if and says this: Binary operator '==' cannot be applied to operands of type 'votes' and 'String'"

推荐答案

我会这样写:

// Precondition: the array is sorted by ascending elements
extension Array where Element: Comparable {
    func binarySearchForIndex(of desiredElement: Element) -> Int? {
        return binarySearchForIndex(of: desiredElement, by: {$0})
    }
}

// Precondition: the array is sorted by ascending values of the picker closure.
extension Array {
    func binarySearchForIndex<T>(
        of desiredElement: T,
        by picker: (Element) -> T
    ) -> Int?
    where T: Comparable {
        var lowerIndex = 0;
        var upperIndex = self.count - 1

        while (true) {
            let currentIndex = (lowerIndex + upperIndex)/2
            let item = picker(self[currentIndex])

            if item == desiredElement { return currentIndex }
            else if lowerIndex > upperIndex { return nil }
            else {
                if (item > desiredElement) {
                    upperIndex = currentIndex - 1
                } else {
                    lowerIndex = currentIndex + 1
                }
            }
        }
    }
}

第一个扩展允许您直接对 Comparable 项的任何 Array 进行二进制搜索.

The first extension allows you to do binary search over any Array of Comparable items directly.

第二个扩展允许您对任何 Array 项进行二进制搜索，提供一个闭包，指定您要搜索元素的哪些属性.你可以这样做:

The second extension allows you do binary search over any Array of items, providing a closure which specifies which of the element's properties you want to search for. You could do something like:

let indexOfBobsVote = votes
    .sorted{ $0.nameSubject < $0.nameSubject}
    .binarySearchForIndex(of: "bob", by: { $0.nameSubject })

这篇关于二分查找:传递数组时出错的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！