如何对 Scala 中的对象列表执行二分搜索

Question

case class Employee (id: Int, name : String, age : Int)

// Added four emplyees emp1, emp2 emp3, emp4 to the list like below::

val emp1 = Employee(101, "name1", 101)
val emp2 = Employee(102, "name2", 102)
val emp3 = Employee(103, "name3", 103)
val emp4 = Employee(104, "name4", 104)

list = scala.List(emp1, emp2, emp3, emp4)

我想使用 BINARY SEARCH 在列表中按姓名搜索员工，并检索该员工对象。

注意：搜索复杂度应该是 O(logn) 并且我们不应该为此使用任何地图。

就像是

val emp = list.binarysearch("name2")
println("the returned employee's age: ", emp.age) //should print 102

任何帮助，将不胜感激。！

Answer 1

搜索提供二进制搜索，但您需要一个索引序列，而不是线性序列（即List），正如其他人所解释的那样 - 否则您仍然可以使用search但您会获得线性 O(n) 行为而不是 O(Log n)。

你说你想搜索姓名，所以你需要按姓名排序，否则你的结果可能会不一致。你应该研究scala.math.Ordering

因此，如果您可以将列表转换为数组，那么您就可以做到这一点。

case class Employee (id: Int, name : String, age : Int)
val emp1 = Employee(1, "Jane Doe", 45)
val emp2 = Employee(2, "Jon Doe", 54)
val emp3 = Employee(3, "Tera Patrick", 38)
val emp4 = Employee(4, "Jenna Jameson", 36)
// convert to an array
val employees = List(emp1, emp2, emp3, emp4).toArray

// define your ordering
import scala.math.Ordering
implicit object NameOrdering extends Ordering[Employee] {
  def compare(a:Employee, b:Employee) = a.name compare b.name
}

// now sort
import scala.util.Sorting
Sorting.quickSort(employees)(NameOrdering)

进而。

import scala.collection.Searching._

// If the element is found its index is returned
scala> val result = employees.search(emp3)
result: collection.Searching.SearchResult = Found(3)

要检索元素，请使用insertionPoint结果的方法。

scala> employees(result.insertionPoint)
res6: Employee = Employee(3,Tera Patrick,38)

如果未找到该元素，则返回其在排序序列中的插入点的索引。

val emp5 = Employee(5, "Aurora Snow", 34)     // not added

scala> employees.search(emp5)
res2: collection.Searching.SearchResult = InsertionPoint(0)