Navi - 2 months ago 21

Swift Question

I am trying to convert the following Swift 2.3 code:

`//Example usage:`

//(0 ..< 778).binarySearch { $0 < 145 } // 145

extension CollectionType where Index: RandomAccessIndexType {

/// Finds such index N that predicate is true for all elements up to

/// but not including the index N, and is false for all elements

/// starting with index N.

/// Behavior is undefined if there is no such N.

func binarySearch(predicate: Generator.Element -> Bool)

-> Index {

var low = startIndex

var high = endIndex

while low != high {

let mid = low.advancedBy(low.distanceTo(high) / 2)

if predicate(self[mid]) {

low = mid.advancedBy(1)

} else {

high = mid

}

}

return low

}

}

into Swift 3 as follows:

`//Example usage:`

//(0 ..< 778).binarySearch { $0 < 145 } // 145

extension Collection where Index: Strideable {

/// Finds such index N that predicate is true for all elements up to

/// but not including the index N, and is false for all elements

/// starting with index N.

/// Behavior is undefined if there is no such N.

func binarySearch(predicate: (Generator.Element) -> Bool)

-> Index {

var low = startIndex

var high = endIndex

while low != high {

let mid = low.advanced(by: low.distance(to: high) / 2)

if predicate(self[mid]) {

low = mid.advanced(to: 1)

} else {

high = mid

}

}

return low

}

}

The error

Binary operator '/' cannot be applied to operands of type 'self.Index.Stride' and 'Int'

is thrown at

`let mid = low.advanced(by: low.distance(to: high) / 2)`

Any help on how to fix it?

Answer

In Swift 3, "Collections move their index", compare
A New Model for Collections and Indices on Swift evolution. In particular, you don't call `advancedBy()`

on an index,
but an `index()`

method on the collection to advance indices.

So your method would be implemented in Swift 3 as

```
extension Collection {
func binarySearch(predicate: (Iterator.Element) -> Bool) -> Index {
var low = startIndex
var high = endIndex
while low != high {
let mid = index(low, offsetBy: distance(from: low, to: high)/2)
if predicate(self[mid]) {
low = index(after: mid)
} else {
high = mid
}
}
return low
}
}
```

without requiring any restrictions on the index type.