Kotlin binarySearch Function | Efficiently Search in Lists in Kotlin

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

The binarySearch function in Kotlin is used to perform a binary search on a sorted list to find the index of a specified element. This function belongs to the List interface in the Kotlin standard library and provides an efficient way to search for elements in a sorted list.

Introduction
binarySearch Function Syntax
Understanding binarySearch
Examples
- Basic Usage
- Using binarySearch with a Comparator
- Searching in a Range
Real-World Use Case
Conclusion

Introduction

The binarySearch function is an efficient search algorithm that works on sorted lists. It repeatedly divides the list in half to narrow down the search range, making it much faster than a linear search for large datasets.

binarySearch Function Syntax

The syntax for the binarySearch function is as follows:

fun <T> List<out T>.binarySearch(element: T, comparator: Comparator<in T>? = null): Int
fun <T> List<out T>.binarySearch(fromIndex: Int, toIndex: Int, element: T, comparator: Comparator<in T>? = null): Int

Parameters:

element: The element to search for.
comparator: An optional comparator to determine the order of the elements. If not provided, natural ordering is used.
fromIndex: The start index (inclusive) of the range to search within.
toIndex: The end index (exclusive) of the range to search within.

Returns:

The index of the element if it is found, otherwise a negative value indicating the insertion point where the element should be.

Understanding binarySearch

The binarySearch function requires the list to be sorted. It works by comparing the middle element of the search range with the target element and narrowing down the search range based on the comparison result. If the element is found, it returns the index of the element. If not, it returns a negative value representing the insertion point.

Examples

Basic Usage

To demonstrate the basic usage of binarySearch, we will search for an element in a sorted list.

Example

fun main() {
    val numbers = listOf(1, 3, 5, 7, 9)
    val index = numbers.binarySearch(5)
    println("Index of element 5: $index")
}

Output:

Index of element 5: 2

Using `binarySearch` with a Comparator

This example shows how to use binarySearch with a custom comparator to search for an element in a sorted list of strings.

Example

fun main() {
    val words = listOf("apple", "banana", "cherry", "date")
    val index = words.binarySearch("cherry", compareBy { it.length })
    println("Index of element 'cherry': $index")
}

Output:

Index of element 'cherry': 2

Searching in a Range

This example demonstrates how to use binarySearch to search for an element within a specified range in a sorted list.

Example

fun main() {
    val numbers = listOf(1, 3, 5, 7, 9, 11, 13)
    val index = numbers.binarySearch(7, fromIndex = 2, toIndex = 5)
    println("Index of element 7 in range 2 to 5: $index")
}

Output:

Index of element 7 in range 2 to 5: 3

Real-World Use Case

Searching for a Student in a Sorted List

In real-world applications, the binarySearch function can be used to efficiently search for elements in sorted datasets, such as finding a student's ID in a sorted list of IDs.

Example

fun main() {
    val studentIds = listOf(101, 203, 305, 407, 509)
    val studentIdToFind = 407
    val index = studentIds.binarySearch(studentIdToFind)

    if (index >= 0) {
        println("Student ID $studentIdToFind found at index: $index")
    } else {
        println("Student ID $studentIdToFind not found. Insert at index: ${-index - 1}")
    }
}

Output:

Student ID 407 found at index: 3

Conclusion

The binarySearch function in Kotlin allows for efficient searching within sorted lists by using binary search. It quickly finds the index of a specified element or returns a negative value if the element is not present, optimizing search operations on large datasets.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Spring Boot + RabbitMQ Course - The Practical Guide