在集合类型中包含着一个Indices属性，这个indices集合记录着集合的下标访问顺序，比方说我们用
Range类型对象构造一个Indices集合，然后这样遍历。
for idx in 0..<someCollection.count {
}
其实我们完全可以用这样的写法：
for idx in someCollection.indices {
}
给数组扩展一个二分查找方法
特别对于数组类型的集合，0..< someCollection.count 与 someCollection.indices几乎就是一样。看起来很美好的样子，但其实只要我们深入一步，麻烦就会来了。让我们从给一个Array增加一个二分查找方法开始说起。
extension Array where Element: Comparable {
public func binarySearch(element: Generator.Element) -> Int? {
var left = 0
var right = count - 1
while left <= right {
let mid = (left + right) / 2
let candidate = self[mid]
if candidate < element {
left = mid + 1
}
else if element < candidate {
right = mid - 1
}
else {
return mid
}
}
return nil
}
}
注意：二分查找算法从被设计出来到第一个正确的算法实现之间间隔了15年，我们今天不考虑算法的正确性，我们只是借用它说明集合索引和泛型的问题。
我们需要要求数组元素准守Comparable协议，太棒了，现在我们的数组有二分查找方法了。
var array = [1,2,3,4,5,6,7,8]
array.binarySearch(4) // 返回索引位置3
将查找方法扩大到CollectionType类型
其实，实事求是的讲，我们现在的做法是基于一定的巧合的，这个巧合在于数组的索引下标是数字的（数组的indices），并且从0开始的，二分查找算法会反复利用下标的位置。如果我们想把二分查找推广到所有集合类，那么我么就会遇到一些问题。如果集合对应的indice是不是整型，那么算法就会出现问题，所以我们需要在进一步处理。
extension CollectionType where Index == Int,Generator.Element:Comparable {
// same as before
}
上面这段代码片段完全可以工作，我们约束集合类型的索引必须是Int类型，并且元素准守Comparable协议。这样的确可以将二分查找法的使用范围进一步扩大了，但我们再思考一下会发现，集合的索引类型只要准守 RandomAccessIndexType 不就可以了吗？我们可以试一下：
extension CollectionType where Index: RandomAccessIndexType ,Generator.Element:Comparable {
public func binarySearch(element: Generator.Element) -> Index? {
var left = startIndex
var right = endIndex.predecessor()
while left <= right {
let mid = (left + right) / 2
let candidate = self[mid]
if candidate < element {
left = mid + 1
}
else if element < candidate {
right = mid - 1
}
else {
return mid
}
}
return nil
}
}
我们在这段代码里做了几处调整：
- Index: RandomAccessIndexType 既将集合的索引类型扩大为RandomAccessIndexType类型
- binarySearch方法的返回值类型 返回 Index?类型。
- var left = startIndex 左起点的位置使用 startIndex进行赋值
- var right = endIndex.predecessor() 右终点的位置用endIndex.predecessor()进行设置
计算索引之间的距离
尽管做了不少努力，我们还是遇到了一个错误： let mid = (left + right) / 2 在这里，由于索引已经不是Int类型了(left,right是RandomAccessIndexType类型)，因此加号+在这里已经不能够工作了。
我们在这里再开动一次脑筋，在二分查找算法里，我们计算left + right的目的是为了得到两个点之间的距离，其实RandomAccessIndexType类型虽然不能直接进行加法操作，但实际上确可以计算两点之间的距离。我们可以把距离的计算方法调整为下面这样：
let mid = startIndex.advancedBy(
( startIndex.distanceTo(left)
+ startIndex.distanceTo(right)
) / 2)
startIndex.distanceTo(left) 我们通过 distanceTo 方法将起始位置(startIndex)到left的位置的距离转换为Int类型数字，所以让加法操作可行了。现在我们成功的获得了使用集合范围的二分查找算法。
其实到这这里，二分查找算法的工作已经完成了，如果我们希望更进一步改善代码，我们可以这样做。
extension Range {
var mid: Element {
return startIndex.advancedBy(
startIndex.distanceTo(endIndex) / 2
)
}
}
我们在扩展Range，并定义mid方法，将求中点的操作定义为Range的方法，这样我们可以把二分查找法的加法操作剥离出来，因此我们在二分查找方法直接调用mid方法。
extension CollectionType where Index: RandomAccessIndexType ,Generator.Element:Comparable {
public func binarySearch(element: Generator.Element) -> Index? {
var searchRegion = self.indices
while left <= right {
let mid = searchRegion.mid
let candidate = self[mid]
if candidate < element {
left = mid + 1
}
else if element < candidate {
right = mid - 1
}
else {
return mid
}
}
return nil
}
}
总结
八条8tiao，没有总结
本文参考链接
http://swiftdoc.org/v2.2/protocol/RandomAccessIndexType/
https://airspeedvelocity.net/2015/12/28/collection-indices-slices-and-generics/
网友评论