跳转至

21.二进制搜索的挑战

挑战1：二进制搜索是一个自由函数

在上一章中，你实现了二进制搜索，作为RandomAccessCollection协议的一个扩展。由于二进制搜索只对排序的集合起作用，将该函数作为RandomAccessCollection的一部分公开，将有机会被滥用。

你的挑战是将二进制搜索作为一个自由函数来实现。

挑战2：搜索一个范围

编写一个函数，搜索一个sorted的数组，找出某个特定元素的索引范围。例如：

let array = [1, 2, 3, 3, 3, 4, 5, 5]
findIndices(of: 3, in: array)

findIndices应该返回2..<5的范围，因为这些是3值的开始和结束索引。

解决方案

挑战1的解决方案

在这个挑战中，你要用一个自由函数实现二进制搜索。下面是这个函数的样子：

func binarySearch<Elements: RandomAccessCollection>(
  for element: Elements.Element,
  in collection: Elements,
  in range: Range<Elements.Index>? = nil) -> Elements.Index?
  where Elements.Element: Comparable {

  let range = range ?? collection.startIndex..<collection.endIndex
  guard range.lowerBound < range.upperBound else {
    return nil
  }
  let size = collection.distance(from: range.lowerBound,
                                 to: range.upperBound)
  let middle = collection.index(range.lowerBound, offsetBy: size / 2)
  if collection[middle] == element {
    return middle
  } else if collection[middle] > element {
    return binarySearch(for: element, in: collection, in: range.lowerBound..<middle)
  } else {
    return binarySearch(for: element,
                        in: collection,
                        in: collection.index(after: middle)..<range.upperBound)
  }
}

挑战2的解决方案

一个未经优化但优雅的解决方案是非常简单的：

func findIndices(of value: Int, in array: [Int]) -> Range<Int>? {
  guard let leftIndex = array.firstIndex(of: value) else {
    return nil
  }
  guard let rightIndex = array.lastIndex(of: value) else {
    return nil
  }
  return leftIndex..<rightIndex
}

这个解决方案的时间复杂度是O(n)，这似乎不是一个值得关注的问题。然而，该方案可以被优化为O(_log n)时间复杂度的方案。

二进制搜索是一种识别sorted集合中的值的算法，所以只要问题承诺是一个排序的集合，就要记住这一点。你在理论章节中实现的二进制搜索不够强大，无法推理出索引是起始索引还是结束索引。你要修改你学过的二进制搜索来适应这个新规则。

在你的Playground上写下以下内容：

func findIndices(of value: Int,
                 in array: [Int]) -> CountableRange<Int>? {
  guard let startIndex = startIndex(of: value,
                                    in: array,
                                    range: 0..<array.count) else {
    return nil
  }
  guard let endIndex = endIndex(of: value,
                                in: array,
                                range: 0..<array.count) else {
    return nil
  }
  return startIndex..<endIndex
}

func startIndex(of value: Int,
                in array: [Int],
                range: CountableRange<Int>) -> Int {
  // more to come
}

func endIndex(of value: Int,
              in array: [Int],
              range: CountableRange<Int>) -> Int {
  // more to come
}

这一次，findIndices将使用专门的二进制搜索。startIndex和endIndex将是用定制的二进制搜索来完成重任。你将修改二进制搜索以检查相邻的值（取决于你寻找的是起始索引还是结束索引）是否与当前值不同。将startIndex方法更新为以下内容：

func startIndex(of value: Int,
                in array: [Int],
                range: CountableRange<Int>) -> Int? {
  // 1
  let middleIndex = range.lowerBound +
                    (range.upperBound - range.lowerBound) / 2

  // 2
  if middleIndex == 0 || middleIndex == array.count - 1 {
    if array[middleIndex] == value {
      return middleIndex
    } else {
      return nil
    }
  }

  // 3
  if array[middleIndex] == value {
    if array[middleIndex - 1] != value {
      return middleIndex
    } else {
      return startIndex(of: value,
                        in: array,
                        range: range.lowerBound..<middleIndex)
    }
  } else if value < array[middleIndex]  {
    return startIndex(of: value,
                      in: array,
                      range: range.lowerBound..<middleIndex)
  } else {
    return startIndex(of: value,
                      in: array,
                      range: middleIndex..<range.upperBound)
  }
}

下面是你用这个代码做的事情：

  1. 你开始计算range中包含的指数的中间值。
  2. 这是这个递归函数的基本情况。如果中间索引是数组的第一个或最后一个可访问的索引，你就不需要再调用二进制搜索。你将确定当前的索引是否是给定值的有效边界。
  3. 在这里，你检查索引处的值，并进行你的递归调用。如果middleIndex处的值等于你给定的值，你就检查前身是否也是相同的值。如果不是，你就知道你已经找到了起始边界。否则，你将继续递归调用startIndex。

endIndex方法也是类似的。将endIndex的实现更新为以下内容：

func endIndex(of value: Int,
              in array: [Int],
              range: CountableRange<Int>) -> Int? {
  let middleIndex = range.lowerBound +
                    (range.upperBound - range.lowerBound) / 2

  if middleIndex == 0 || middleIndex == array.count - 1 {
    if array[middleIndex] == value {
      return middleIndex + 1
    } else {
      return nil
    }
  }

  if array[middleIndex] == value {
    if array[middleIndex + 1] != value {
      return middleIndex + 1
    } else {
      return endIndex(of: value,
                      in: array,
                      range: middleIndex..<range.upperBound)
    }
  } else if value < array[middleIndex]  {
    return endIndex(of: value,
                    in: array,
                    range: range.lowerBound..<middleIndex)
  } else {
    return endIndex(of: value,
                    in: array,
                    range: middleIndex..<range.upperBound)
  }
}

在Playground的底部写下以下内容，测试一下你的解决方案。

let array = [1, 2, 3, 3, 3, 4, 5, 5]
if let indices = findIndices(of: 3, in: array) {
  print(indices)
}

你应该在控制台看到以下输出：

2..<5

这个函数将时间复杂度从O(n)提高到O(log n)。