searchWhenSorted.swift

extension CollectionType where Generator.Element: Comparable {
  func searchWhenSorted(toFind: Generator.Element) -> Self.Index? {
    return self.order.flatMap {
      (order: ((Generator.Element, Generator.Element) -> Bool)) -> Index? in
      for (index, element) in zip(self.indices, self) {
        if element == toFind {
          return index
        } else if order(toFind, element) {
          return nil
        }
      }
      return nil
    }
  }
  func searchWhenSorted(
    toFind: Generator.Element,
    isOrderedBefore: ((Generator.Element, Generator.Element) -> Bool)
    ) -> Index? {
    for (index, element) in zip(self.indices, self) {
      if element == toFind {
        return index
      } else if isOrderedBefore(toFind, element) {
        return nil
      }
    }
    return nil
  }
}

extension SequenceType where Generator.Element: Comparable {
  var order: ((Generator.Element, Generator.Element) -> Bool)? {
    var g = self.generate()
    var last = g.next()
    
    for (var next = g.next();last != nil;last = next, next = g.next()) {
      if next != last {
        return next > last ?
          {(a: Generator.Element, b: Generator.Element) -> Bool in a < b} :
          {(a: Generator.Element, b: Generator.Element) -> Bool in a > b}
      }
    }
    return nil
  }
}