Binary search: error in passing array

Question

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
            }
        }
    }
}

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'"

If you're doing this often, you're better off making a Dictionary mapping nameSubject to votes objects — Alexander
– Alexander, Commented Jun 29, 2017 at 18:04
As an aside, Swift's convention is to have UpperCamelCase, singular named types, such as Vote — Alexander
– Alexander, Commented Jun 29, 2017 at 18:05

Alexander · Accepted Answer · 2017-06-29 18:10:21Z

Here is how I would write this:

// 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
                }
            }
        }
    }
}

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

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 })

Ken Darragh · Accepted Answer · 2017-06-29 17:55:07Z

0

You should compare the string with the object's nameSubject string, not the object itself.

So the comparison you should make is:

inputArr[currentIndex].nameSubject == searchItem

Although this will not help with the comparison you're making after that. I'm not sure what property you are trying to evaluate with the ">"

answered Jun 29, 2017 at 17:55

Ken Darragh

597 bronze badges

Collectives™ on Stack Overflow

Binary search: error in passing array

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related