Sequential Search in Kotlin

okuzawats
okuzawats

Sequential search, or Linear search is an algorithm to find an element from array. The array is usually not sorted, because there are algorithms that is faster than sequential search if the array is sorted.

Sequential search compares all the elements from the start of the target array until the target element is found or ends up at the end of the array. So the algorithm compares (n + 1) / 2 times on average to find the element, and the order is O(n). Basically, it ignores the duplication of the target element. If the same value is in one array, the basic sequential search returns the index of the first element equal to the target element.

Below is an implementation of sequential search in Kotlin.

fun find(target: T): Result {
  for (i in from.indices) {
    if (target == from[i]) {
      return Result.Found(index = i)
    }
  }
  return Result.NotFound
}

from is an array of any types. If the target is found in the array, it returns Result.Found, which has the index of the element found. If the target is not found in the array, it returns Result.NotFound.


The entire code is below:

fun main (args: Array<String>) {
  // from Yazawa (2019)
  val from = arrayOf<Int>(72, 68, 92, 88, 41, 53, 97, 84, 39, 55)
  val sequentialSearch = SequentialSearch<Int>(from = from)

  val result1 = sequentialSearch.find(target = 53)
  check(result1 is SequentialSearch.Result.Found && result1.index == 5)

  val result2 = sequentialSearch.find(target = 39)
  check(result2 is SequentialSearch.Result.Found && result2.index == 8)

  val result3 = sequentialSearch.find(target = 99)
  check(result3 is SequentialSearch.Result.NotFound)
}

/**
 * A class that supports sequential search
 *
 * @param from target array of [T]
 * @param T type of target array items
 */
class SequentialSearch<T>(
  private val from: Array<T>
) {
  /**
   * A sealed class that represents the result of sequential search
   */
  sealed class Result {
    /**
     * Found target item in the array [from]
     *
     * @param index of the item found
     */
    data class Found(val index: Int) : Result()

    /**
     * Not found target item in the array [from]
     */
    object NotFound : Result()
  }

  /**
   * try to find [target] from the array [from]
   *
   * @param target the item to find from the array
   * @return if [target] found, returns [Result.Found], or returns [Result.NotFound]
   */
  fun find(target: T): Result {
    for (i in from.indices) {
      if (target == from[i]) {
        return Result.Found(index = i)
      }
    }
    return Result.NotFound
  }
}

References: