Kotlin Comparator Binary Search for Object List

In the tutorial, JavaSampleApproach will show you how to look up an element in an object list with Kotlin Comparator Binary Search.

Related posts:
Kotlin – Sort List of Objects with Kotlin Comparator Example
Kotlin Comparable Binary Search for Object List
Kotlin Binary Search for Object List with Comparison function – comparison: (T) -> Int
Kotlin Binary Search for Object List with Selector function – crossinline selector: (T) -> K?

I. Technologies

– Kotlin 1.1.61
– Java 8

II. Kotlin Comparator Binary Search

Step to do:
– Create data model & Comparator
– Create a sorted list
– Do Binary Search

1. Create data model & Comparator

– Create Product data model:


data class Product(val name: String, val price: Double /*USD*/)

– Create a Comparator:


class CompareObjects {
	companion object : Comparator {
		override fun compare(p1: Product, p2: Product): Int = (p1.price - p2.price).toInt()
	}
}

2. Create a sorted list

We can use Iterable.sortedWith(comparator: Comparator) to sort an Object List.
-> Detail method signature:

public fun  Iterable.sortedWith(comparator: Comparator): List

val products = listOf(Product("iPhone 8 Plus 64G", 850.00),
						Product("iPhone 8 Plus 256G", 1100.00),
						Product("Apple iPod touch 16GB", 246.00),
						Product("Apple iPod Nano 16GB", 234.75),
						Product("iPad Pro 9.7-inch 32 GB", 474.98),
						Product("iPad Pro 9.7-inch 128G", 574.99),
						Product("Apple 42mm Smart Watch", 284.93))

val sortedProducts = products.sortedWith(CompareObjects)
println(sortedProducts)
// print on console an ascending product list:
/*
	[Product(name=Apple iPod Nano 16GB, price=234.75),
		Product(name=Apple iPod touch 16GB, price=246.0),
		Product(name=Apple 42mm Smart Watch, price=284.93),
		Product(name=iPad Pro 9.7-inch 32 GB, price=474.98),
		Product(name=iPad Pro 9.7-inch 128G, price=574.99),
		Product(name=iPhone 8 Plus 64G, price=850.0),
		Product(name=iPhone 8 Plus 256G, price=1100.0)]
*/

More at: Kotlin – Sort List of Objects with Kotlin Comparator Example
3. Comparator Binary Search

We use below method signature for Comparator Binary Search:

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

The Comparable Binary Search will search the sorted list or its range for the provided element using the binary search algorithm.
It will return the index of given element. Otherwise, it will return the inverted insertion point (-insertion point – 1).

Note: The list is expected to be sorted into ascending order according to the specified [comparator]

What is insertion point?
-> The insertion point is defined as the index at which the given element should be inserted for the list (or specified range of list) still remains sorted.


//	Use binarySearch() method signature as below: 
//	-> public fun  List.binarySearch(element: T, comparator: Comparator, fromIndex: Int = 0, toIndex: Int = size): Int
val index = sortedProducts.binarySearch(Product("", 284.93), CompareObjects)
println("index = $index"); // index = 2
println(sortedProducts.get(index)) // Product(name=Apple 42mm Smart Watch, price=284.93)

// We can use fromIndex & toIndex parameters
/*
 * From 0 -> 3: we find out the product with price = 284.93
 */	
val index2 = sortedProducts.binarySearch(Product("", 284.93), CompareObjects, 0, 3)
println("index2 = $index2"); // index2 = 2
println(sortedProducts.get(index2)) // Product(name=Apple 42mm Smart Watch, price=284.93)

/*
 * So from 3 -> (toIndex: Int = size): we can NOT find out the product with price = 284.93
 */	
val index3 = sortedProducts.binarySearch(Product("", 284.93), CompareObjects, 3)
println("index3 = $index3"); // index3 = -4	

III. Full Sourcecode


package com.javasampleapproach.binarysearch

data class Product(val name: String, val price: Double /*USD*/)

class CompareObjects {
	companion object : Comparator {
		override fun compare(p1: Product, p2: Product): Int = (p1.price - p2.price).toInt()
	}
}

fun main(args : Array){
	val products = listOf(Product("iPhone 8 Plus 64G", 850.00),
							Product("iPhone 8 Plus 256G", 1100.00),
							Product("Apple iPod touch 16GB", 246.00),
							Product("Apple iPod Nano 16GB", 234.75),
							Product("iPad Pro 9.7-inch 32 GB", 474.98),
							Product("iPad Pro 9.7-inch 128G", 574.99),
							Product("Apple 42mm Smart Watch", 284.93))
	
	val sortedProducts = products.sortedWith(CompareObjects)
	println(sortedProducts)
	// print on console an ascending product list:
	/*
 		[Product(name=Apple iPod Nano 16GB, price=234.75),
 			Product(name=Apple iPod touch 16GB, price=246.0),
 			Product(name=Apple 42mm Smart Watch, price=284.93),
 			Product(name=iPad Pro 9.7-inch 32 GB, price=474.98),
 			Product(name=iPad Pro 9.7-inch 128G, price=574.99),
 			Product(name=iPhone 8 Plus 64G, price=850.0),
 			Product(name=iPhone 8 Plus 256G, price=1100.0)]
 	*/
	
	//	Use binarySearch() method signature as below: 
	//	-> public fun  List.binarySearch(element: T, comparator: Comparator, fromIndex: Int = 0, toIndex: Int = size): Int
	val index = sortedProducts.binarySearch(Product("", 284.93), CompareObjects)
	println("index = $index"); // index = 2
	println(sortedProducts.get(index)) // Product(name=Apple 42mm Smart Watch, price=284.93)
	
	// We can use fromIndex & toIndex parameters
	/*
	 * From 0 -> 3: we find out the product with price = 284.93
	 */	
	val index2 = sortedProducts.binarySearch(Product("", 284.93), CompareObjects, 0, 3)
	println("index2 = $index2"); // index2 = 2
	println(sortedProducts.get(index2)) // Product(name=Apple 42mm Smart Watch, price=284.93)
	
	/*
	 * So from 3 -> (toIndex: Int = size): we can NOT find out the product with price = 284.93
	 */	
	val index3 = sortedProducts.binarySearch(Product("", 284.93), CompareObjects, 3)
	println("index3 = $index3"); // index3 = -4	
}


By grokonez | December 15, 2017.

Last updated on April 17, 2021.



Related Posts


Got Something To Say:

Your email address will not be published. Required fields are marked *

*