Linear Search in Kotlin : Pros and Cons

Linear Search in a straightforward searching algorithm used to find an element within a collection, typically an array or a list. Let’s explore linear search in Kotlin with examples.

How does this mechanism work?

It works by iterating through each element of the collection until the desired element is found or the entire collection has been traversed.

Matching

For each element in the collection/array, the algorithm compares the current element with the target element that needs to be found. If the current element matches the target element, the search process ends, and the index where the element was found is returned. If the element is not found after checking all elements, the search concludes, indicating that the element does not exist in the collection/array.

Linear Search traverses elements one by one in sequence until the desired element is found or the end of the collections is reached. It works with both ordered and unordered collections. However, for an ordered collections, other search algorithms like binary search could be more efficient.

Linear Search : Kotlin Example

Let’s say we have a Kotlin array ‘[4, 2, 7, 1, 9, 5]‘ and we want to search for the element ‘7‘.

fun main() {
    
    val array = arrayOf(4, 2, 7, 1, 9, 5)
    val search = linearSearch(array,array.size,7)
    if(search == 1) 
    println("The element is found" ) 
    else 
    println("The element is not found")
    
}

fun linearSearch(array: Array<Int>, size:Int, element:Int): Int
{
   for(i in 0 until size){
       if(array[i] == element) return 1
   } 
   return -1 
}

The element is found

Linear Search will start at the beginning of the Kotlin array and check each element sequentially. It compares each element with ‘7‘. Here, when it reaches the third element ‘7’, it identifies a match and returns ‘1’ as specified in the function definition. If it returns 1 then it will print the message ‘The element is found’ on the console.

Complexity

Time Complexity

O(n) in the worst case, where n is the number of elements in the collection. It needs to traverse all elements if the target element is at the end or not present.

Space complexity

O(1) as it doesn’t require additional space proportional to the input size.

Example 2: Printing the indices

Open the Kotlin Playground and write the following code:

fun main() {
    val numbers = arrayOf(5, 6, 7)
    searchAndPrintIndex(numbers, 5)
}

fun searchAndPrintIndex(array: Array<Int>, element: Int) {
    for (i in array.indices) {
        if (array[i] == element) {
            println("Element $element found at index: $i")
            return
        }
    }
    println("Element $element not found in the array.")
}

Element 5 found at index: 0

Pros and Cons of Linear Search

The implementation of Linear Search is super easy. The linear search often use this approach when dealing with small or unsorted collections and when efficiency isn’t crucial. For larger or sorted collections, they might prefer more optimized algorithms like Binary Search because of their faster search times.