Search Algorithms in Kotlin: A Comprehensive Guide

Linear Search

Overview

Linear search (or sequential search) is the simplest search algorithm that works by checking every element in a collection until a match is found or the entire collection has been searched.

Implementation

fun <T> List<T>.linearSearch(element: T): Int {
    for (i in this.indices) {
        if (this[i] == element) {
            return i
        }
    }
    return -1
}

// Generic implementation with predicate
fun <T> List<T>.linearSearchBy(predicate: (T) -> Boolean): Int {
    for (i in this.indices) {
        if (predicate(this[i])) {
            return i
        }
    }
    return -1
}

Advanced Implementations

Parallel Linear Search

fun <T> List<T>.parallelLinearSearch(element: T): Int = runBlocking {
    if (size <= 1000) return@runBlocking linearSearch(element)

    val numberOfThreads = Runtime.getRuntime().availableProcessors()
    val chunkSize = size / numberOfThreads

    val deferreds = List(numberOfThreads) { threadIndex ->
        async(Dispatchers.Default) {
            val startIndex = threadIndex * chunkSize
            val endIndex = if (threadIndex == numberOfThreads - 1) size else startIndex + chunkSize

            for (i in startIndex until endIndex) {
                if (this@parallelLinearSearch[i] == element) return@async i
            }
            return@async -1
        }
    }

    deferreds.awaitAll().firstOrNull { it != -1 } ?: -1
}

Early-Stopping Linear Search

fun <T> List<T>.linearSearchWithEarlyStop(
    element: T,
    shouldStop: (T) -> Boolean
): Int {
    for (i in this.indices) {
        if (this[i] == element) return i
        if (shouldStop(this[i])) break
    }
    return -1
}

Time and Space Complexity

Time Complexity

• Best Case: O(1) - Element found at first position
• Average Case: O(n/2) - Element found at middle position
• Worst Case: O(n) - Element not found or at last position

Space Complexity

• O(1) - Constant space regardless of input size

Performance Analysis

fun analyzeSingleLinearSearch(size: Int): Long {
    val list = List(size) { it }
    val target = size - 1  // Worst case scenario

    val startTime = System.nanoTime()
    list.linearSearch(target)
    return System.nanoTime() - startTime
}

data class PerformanceMetrics(
    val size: Int,
    val bestCase: Long,
    val averageCase: Long,
    val worstCase: Long
)

fun generatePerformanceTable(): List<PerformanceMetrics> {
    return listOf(100, 1000, 10000, 100000).map { size ->
        val list = List(size) { it }

        val bestCase = measureNanoTime { list.linearSearch(0) }
        val averageCase = measureNanoTime { list.linearSearch(size / 2) }
        val worstCase = measureNanoTime { list.linearSearch(size - 1) }

        PerformanceMetrics(size, bestCase, averageCase, worstCase)
    }
}

Binary Search

Overview

Binary search is an efficient algorithm for searching a sorted array by repeatedly dividing the search interval in half. It works on the principle of divide and conquer.

Basic Implementation

fun <T : Comparable<T>> List<T>.binarySearch(element: T): Int {
    var low = 0
    var high = size - 1

    while (low <= high) {
        val mid = (low + high) / 2
        when {
            this[mid] == element -> return mid
            this[mid] > element -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return -1
}

Advanced Implementations

Recursive Binary Search

fun <T : Comparable<T>> List<T>.binarySearchRecursive(
    element: T,
    low: Int = 0,
    high: Int = size - 1
): Int {
    if (low > high) return -1

    val mid = (low + high) / 2
    return when {
        this[mid] == element -> mid
        this[mid] > element -> binarySearchRecursive(element, low, mid - 1)
        else -> binarySearchRecursive(element, mid + 1, high)
    }
}

Binary Search with Custom Comparator

fun <T> List<T>.binarySearchBy(
    element: T,
    comparator: Comparator<T>
): Int {
    var low = 0
    var high = size - 1

    while (low <= high) {
        val mid = (low + high) / 2
        val comparison = comparator.compare(this[mid], element)

        when {
            comparison == 0 -> return mid
            comparison > 0 -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return -1
}

Generic Binary Search for Range

fun binarySearchRange(
    start: Int,
    end: Int,
    predicate: (Int) -> Boolean
): Int {
    var low = start
    var high = end

    while (low <= high) {
        val mid = low + (high - low) / 2

        when {
            predicate(mid) -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return low
}

Common Pitfalls and Solutions

1. Integer Overflow

// Incorrect
val mid = (low + high) / 2

// Correct
val mid = low + (high - low) / 2

1. Infinite Loop

// Potential infinite loop
while (low < high)

// Correct
while (low <= high)

1. Off-by-One Errors

// Common mistake
high = mid
low = mid

// Correct
high = mid - 1
low = mid + 1

Performance Comparison

fun compareSearchAlgorithms(size: Int, iterations: Int = 1000): SearchComparison {
    val sortedList = List(size) { it }

    val linearSearchTime = measureNanoTime {
        repeat(iterations) {
            sortedList.linearSearch(size / 2)
        }
    } / iterations

    val binarySearchTime = measureNanoTime {
        repeat(iterations) {
            sortedList.binarySearch(size / 2)
        }
    } / iterations

    return SearchComparison(size, linearSearchTime, binarySearchTime)
}

data class SearchComparison(
    val size: Int,
    val linearSearchTime: Long,
    val binarySearchTime: Long
)

Time and Space Complexity

Binary Search

• Time Complexity:
  • Best Case: O(1) - Element found at middle
  • Average Case: O(log n)
  • Worst Case: O(log n)
• Space Complexity:
  • Iterative: O(1)
  • Recursive: O(log n) due to call stack

Practical Applications

1. Database Indexing

class IndexedDatabase<K : Comparable<K>, V>(
    private val keys: MutableList<K> = mutableListOf(),
    private val values: MutableList<V> = mutableListOf()
) {
    fun insert(key: K, value: V) {
        val index = keys.binarySearch(key).let { 
            if (it < 0) -(it + 1) else it 
        }
        keys.add(index, key)
        values.add(index, value)
    }

    fun find(key: K): V? {
        val index = keys.binarySearch(key)
        return if (index >= 0) values[index] else null
    }
}

1. Range Queries

fun <T : Comparable<T>> List<T>.findRange(
    start: T,
    end: T
): IntRange? {
    val startIndex = binarySearchBy { it >= start }
    if (startIndex == size) return null

    val endIndex = binarySearchBy { it > end }
    if (startIndex >= endIndex) return null

    return startIndex until endIndex
}

Best Practices and Optimization Tips

1. Choose the Right Algorithm:

   • Use Linear Search for:
     • Small datasets (n < 50)
     • Unsorted data
     • When preprocessing overhead matters
   • Use Binary Search for:
     • Large sorted datasets
     • Frequent searches
     • When initial sorting cost is justified

2. Implementation Considerations:

   • Always validate input data
   • Handle edge cases properly
   • Consider using built-in functions for standard cases
   • Use appropriate data types for indices

3. Performance Optimization:

   • Keep data sorted when possible
   • Use iterative implementation for better space complexity
   • Consider parallel search for very large datasets
   • Cache results when appropriate

4. Error Handling:
   

fun <T : Comparable<T>> List<T>.safeBinarySearch(
    element: T
): Result<Int> = runCatching {
    require(isNotEmpty()) { "List is empty" }
    require(isSorted()) { "List must be sorted" }
    binarySearch(element)
}

fun <T : Comparable<T>> List<T>.isSorted(): Boolean =
    zipWithNext { a, b -> a <= b }.all { it }

Comparison Table

Aspect	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Space Complexity	O(1)	O(1)
Prerequisites	None	Sorted data
Best Use Case	Small/unsorted	Large/sorted
Implementation	Simple	More complex
Stability	Stable	Stable
Adaptability	More flexible	Less flexible

Conclusion

Both linear and binary search algorithms have their place in modern software development. Linear search's simplicity makes it ideal for small datasets and unsorted collections, while binary search's efficiency makes it the go-to choice for large, sorted datasets. Understanding the trade-offs and implementation details of both algorithms is crucial for writing efficient and maintainable code.