如何在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

Searching提供了二进制搜索，但你需要一个索引序列，而不是一个线性序列（即.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)

Answer 2

你永远不能在O（log n）中对scala List（）进行二进制搜索，因为我们不能一次丢弃一半的列表，我们必须遍历到中间点。但是可以使用Array完成。在Scala中，您可以创建一个隐式类，以在任何Array [String]实例上具有binarySearch（）方法

  implicit class StrArrayOps(strArray: Array[String]) {
    @scala.annotation.tailrec
    private def bs(arr: Array[String], s: Int, e: Int, str: String): Option[Int] = {
      if (e<s) {
        None
      } else {
        val m = (s+e)/2
        val mid = arr(m)
        if (mid == str) {
          Some(m)
        } else {
          if (str.compareTo(mid) > 0) {
            bs(arr, m+1, e, str)
          } else {
            bs(arr, 0, m-1, str)
          }
        }
      }
    }

    //returns None if str not found in the strArray
    //returns Some(i) where i is the index of str in the strArray
    def binarySearch(str: String): Option[Int] = bs(strArray, 0, strArray.length-1, str)
  }

您可以按如下方式使用它

scala> val a = Array("name1", "name2", "name3")
a: Array[String] = Array(name1, name2, name3)

scala> a.binarySearch("name2")
res20: Option[Int] = Some(1)

scala> a.binarySearch("name1")
res21: Option[Int] = Some(0)

scala> a.binarySearch("name3")
res22: Option[Int] = Some(2)

scala> a.binarySearch("name34")
res23: Option[Int] = None