Как я могу выполнить бинарный поиск по списку объектов в Scala - PullRequest
Новая
       10

Как я могу выполнить бинарный поиск по списку объектов в Scala

0 голосов
/ 11 сентября 2018 
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

Любая помощь будет оценена.!

Ответы [ 2 ]

0 голосов
/ 11 сентября 2018

Поиск обеспечивает бинарный поиск, но вам нужна индексированная последовательность, а не линейная (т. Е. 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)
0 голосов
/ 11 сентября 2018

Вы никогда не сможете выполнить бинарный поиск в Scala List () в O (log n) , так как мы не можем отбросить половину списка за раз, нам нужно пройти до середины для этого , Однако это можно сделать с помощью массива. В Scala вы можете создать неявный класс, чтобы иметь метод binarySearch () в любом экземпляре Array [String] 

  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
...