Kotlin Training Program

DOWNLOAD APP

FEEDBACK

Search

First occurrence

To find the index of a particular element in list, we have the built-in find() function :

 fun main() {
    println(
        listOf(20, 14, 13, 2, 3)
            .find { it % 2 == 1 } // Find the index of first odd number
    ) // Prints 2
}

Note that find() function finds the index of only the first occurrence of element that satisfies the given predicate.

Implementing find() function is straight forward. We just have to iterate through the list and as soon as we find an element that satisfies the predicate, we return its index.

 fun <T> List<T>.findX(predicate: (T) -> Boolean): Int? {
    forEachIndexed { index, i ->
        if (predicate(i)) return index
    }

    return null
}

This is known as Linear search because we iterate through the list in a linear fashion i.e. one index after another.

All occurrences

We can also implement a findAll() function that would return the indices of all matching elements. To do so, we create a list to save the indices and return it :

 fun <T> List<T>.findAll(predicate: (T) -> Boolean): List<Int> {
    return buildList {
        this@findAll.forEachIndexed { index, i ->
            if (predicate(i)) add(index)
        }
    }
}

fun main() {
    println(
        listOf(20, 14, 13, 2, 3)
            .findAll { it % 2 == 1 }
    ) // Prints [2, 4]
}

Time complexity

The time complexity of above find() and findAll() functions is O(n) for a list of size n i.e. in the worst case we may need to go through the entire list to find the element. Here, worst case is when the element is found at the last index or not found at all. However for findAll() function, the runtime is always n i.e. irrespective of whether we find an occurrence, iterating the entire list is required to find all occurrences.

Binary Search

Time complexity of find() function can be reduced using Binary Search if the list is sorted. First lets understand Binary Search in List<Int> and then its generic version.

The basic idea behind Binary Search is to keep dividing the list into two halves and examine the middle element. Lets understand the approach using an example.

Example

Suppose we need to find the index of x=15 in the list = [1, 4, 6, 12, 15, 18, 22]. Following are steps to be followed :

  • To divide the list into two halves, we find the index of middle element. Size of list is 7, begin and end of search space are 0 & 6 respectively. index of middle element can be found as (begin + end) / 2 = (0 + 6) / 2 = 3.
  • Middle element is list[3] = 12. Based on this middle element, we can reduce the search space by half. Middle element 12 indicates that all the numbers in first half [1, 4, 6] are smaller than 12 while all numbers in second half [15, 18, 22] are larger than 12. Since x (15) is larger than 12, we can safely discard the first half [1, 4, 6].
  • Since the first half is discarded, the search space is reduced to second half only [15, 18, 22]. So, begin is now 3 + 1 = 4 while end is still 6. We repeat the same process of splitting and examining the middle element.
  • Index of middle element is (begin + end) / 2 = (4 + 6) / 2 = 5.
  • Middle element is list[5] = 18. Since x (15) is smaller than 18, we can safely discard the second half [22]. Now the search space is reduced to just [15] so end is 5 - 1 = 4 while begin is still 4. We repeat the same process again.
  • Middle element is now list[(4 + 4) / 2 = 4] = 15. Here middle element is equal to the element we are looking for i.e. x (15). So search stops here.

Suppose we have to find x=16, then on the last step, x (16) is larger than middle element (15). So, it might be present in second half hence begin is now 4 + 1 = 5 while end is still 4. Here, begin > end i.e. invalid range for search space. This is another condition where search stops with the result - Not found.

Lets see another example of Not found.

Suppose we have to find x=14, then on the last step, x (14) is smaller than middle element (15). So, it might be present in first half hence end is now 4 - 1 = 3 while begin is still 4. Here also, begin > end i.e. invalid range for search space. So search stops with the result - Not found.

Algorithm

Steps to be followed to find a number x in List<Int> list :

  • Initialize begin = 0, end = list.lastIndex
  • repeat while begin ≤ end :
    • Calculate midIndex as (begin + end) / 2
    • Find mid as list[midIndex]
    • if x equals mid, return midIndex
    • else if x < mid, end = midIndex - 1
    • else x > mid, begin = midIndex + 1
  • return null (x not found)

Implementation

 
 fun List<Int>.binarySearch(x: Int): Int? {
    var begin = 0; var end = lastIndex

    while (begin <= end) {
        val midIndex = (begin + end) / 2
        when {
            // x found
            get(midIndex) == x -> return midIndex

            // x might be in first half
            get(midIndex) > x -> end = midIndex - 1

            // x might be in second half
            else -> begin = midIndex + 1
        }
    }

    // x not found
    return null
}

Time complexity

Time complexity of Binary search is less than that of Linear search. Lets analyze how.

On each iteration, the length of search space is divided by 2 as one half is discarded by analyzing the middle element. There are two worst case scenarios. Firstly, we may find the required element when search space length is just 1 as in above example. Secondly, we may not find the required element i.e. when search space length is 0. For a list of length n, n is divided by 2 on each iteration until we get 0 or 1. This is nothing but log~2~n. Hence, Binary search has logarithmic time complexity. Following is a comparison between the two search algorithms :

List length Linear search ops Binary search ops
10 10 log(10) ≈ 3
100 100 log(100) ≈ 7
1000 1000 log(1000) ≈
10000 10000 log(10000) ≈ 10
1M 1M log(1M) ≈ 20

It is clear that Binary search is way more efficient than Linear search when finding an element in a sorted list.

Generic Binary Search

Binary search is not restricted to List<Int>. We can perform Binary search on list of objects of any class. To sort list of objects, we have to pass an additional parameter - comparator :

 public fun <T> List<T>.binarySearch(
		element: T, 
		comparator: Comparator<in T>, 
		fromIndex: Int = 0, 
		toIndex: Int = size
): Int

Lets see an example of generic Binary Search and then understand what a Comparator is.

Following is an example of Binary Search on List<Planet> :

 class Planet(
    val name: String,
    val mass: Double,
    val radius: Double,
    val distanceFromSun: Double
)

fun main() {
    // Sorted list to search in
    val planets = listOf(
        Planet("Earth", 5.9724e24, 6371.0, 149.6e6),
        Planet("Jupiter", 1.8982e27, 69911.0, 778.6e6),
        Planet("Mars", 6.4171e23, 3389.5, 227.9e6),
        Planet("Mercury", 3.3011e23, 2439.7, 57.91e6),
        Planet("Neptune", 1.0243e26, 24622.0, 4.50e9),
        Planet("Pluto", 1.3030e22, 1188.3, 5.91e9),
        Planet("Saturn", 5.6834e26, 58232.0, 1.43e9),
        Planet("Uranus", 8.6810e25, 25362.0, 2.87e9),
        Planet("Venus", 4.8675e24, 6051.8, 108.2e6)
    )

    // Element to search for
    val mars = Planet("Mars", 6.4171e23, 3389.5, 227.9e6)

    // Perform binary search
    val index = planets.binarySearch(mars, compareBy { it.name })

    // Analyze the result
    if (index < 0) {
        println("${mars.name} was not found in the list.")
    } else {
        println("${mars.name} was found at index $index in the list.")
    }
}

/* Output :
Mars was found at index 2 in the list. */

Note that we have used the compareBy() function to define a comparator for Planet.

Comparator is an interface that needs to be implemented for comparing two objects of same type :

 /**
 * Provides a comparison function for imposing a total ordering between instances of the type [T].
 */
public expect fun interface Comparator<T> {
    /**
     * Compares its two arguments for order. Returns zero if the arguments are equal,
     * a negative number if the first argument is less than the second, or a positive number
     * if the first argument is greater than the second.
     */
    public fun compare(a: T, b: T): Int
}

To implement the Comparator interface, we can use the built-in compareBy() function :

 public fun <T> compareBy(
		selector: (T) -> Comparable<*>?
): Comparator<T>

selector is a lambda to return the value based on which the comparison has to be performed.

Usage :

 planets.binarySearch(mars, compareBy { it.name })