Scala: Linear and Binary Search Implementation

scalaWelcome to my first article on Scala. In this post let’s discuss the implementation of linear and binary search in scala. These are some of the popular searching algorithms. Lets see how to implement them in scala.

Linear Search

Linear search is searching technique that searches for any item serially from the first element until the item is found in any collection. It scans the element one-by-one until the item that is searched matches the item currently scanned. More details here.

Complexity:

Worst case: O(n) => if the item to search is present at last index

Best case: O(1) => if the item to search is present at first index

Code:

object LinearSearch {
  def linearSearch[T](items: List[T], searchElem: T): Boolean = {
    if (items.isEmpty) false
    else if (items.head == searchElem) true
    else linearSearch(items.tail, searchElem)
  }
  def main(args: Array[String]): Unit = {
    println(linearSearch(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 34, 56, 345, 1245), 10))
    println(linearSearch(List("a", "b"), "b"))
    println(linearSearch(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 34, 56, 345, 1245), 15))
  }
}

In above-written code, the search key is compared with the head of list and if they match true is returned otherwise the process continues for the tail of the list recursively until the key is found or the list is empty.

Whenever you run this code, it will print true if the  value is found and false otherwise.

Binary Search

Binary search is a searching technique that divides the given list into two halves and recursively searches in each half by comparing with the given search key. One condition is that the given list must be sorted to apply this algorithm. This algorithm is faster than the linear search since the complete list should not be scanned to find the required item. In each iteration the list is divided which gives the complexity to be O(log n). More details here.

Complexity:

Worst case: O(log n)

Best case: O(1)

Code:

object BinarySearch {
  def binarySearch[T](items: List[T], find: T)(implicit ordering: Ordering[T]): Boolean = {
    if (items.length == 1) {
      if (items.head == find) true else false
    }
    else {
      val midPoint = dividePoint(items)
      val midElem = items.apply(midPoint)
      if (ordering.gt(find, midElem)) binarySearch(items.drop(midPoint), find)
      else if (ordering.gt(midElem, find)) binarySearch(items.take(midPoint), find)
      else true
    }
  }
  def dividePoint[T](items: List[T]): Int = {
    if (items.size % 2 == 0) items.size / 2 else items.size / 2 + 1
  }
  def main(args: Array[String]): Unit = {
    println(binarySearch(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 34, 56, 345, 1245), 10))
    println(binarySearch(List("a", "b"), "b"))
    println(binarySearch(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 34, 56, 345, 1245), 15))
  }
}

Whenever you run this code, it will print true if the  value is found and false otherwise. This code is for the elements that are sorted in ascending order. If you are to implement for the one in descending order, just swap the comparison logic.

I hope this article will be of use. If there are any queries/suggestions please comment them. I’ll see you in the next one. Cheers 🙂

Update: Code is now available on GitHub.
 
 

254 total views, 2 views today

1 comment on “Scala: Linear and Binary Search Implementation

  1. Pingback: How to start writing tests in Scala? – something about a lot of things

Leave a Reply

Your email address will not be published. Required fields are marked *