Kotlin Binary Search for Object List with Comparison function – comparison: (T) -> Int

In the tutorial, JavaSampleApproach will show you how to look up an element in an object list with Kotlin Binary Search for Object List by Comparison function – comparison: (T) -> Int.

Related posts:
Kotlin Sort Object List with Kotlin Selector function – crossinline selector: (T) -> R?
Kotlin Comparator Binary Search for Object List
Kotlin Comparable Binary Search for Object List
Kotlin Binary Search for Object List with Selector function – crossinline selector: (T) -> K?

I. Technologies

– Kotlin 1.1.61
– Java 8

II. Kotlin Binary Search with Comparison function

Step to do:
– Create data model
– Create a sorted list
– Binary Search with Comparison function

1. Create data model

– Create Product data model:

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

Initial Product 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))
2. Create a sorted list

We can use Iterable.sortedBy(crossinline selector: (T) -> R?) to sort an Object List.
-> Detail method signature:

public inline fun > Iterable.sortedBy(crossinline selector: (T) -> R?): List

So we need define a selector function:

fun selector(p: Product): Double = p.price

Then do sorting Product List:

// Use sortedBy() method signature as below:
// -> public inline fun > Iterable.sortedBy(crossinline selector: (T) -> R?): List
val sortedProducts = products.sortedBy({selector(it)})
					// -> simple representation solution
					// val sortedProducts = products.sortedBy{it.price}

More at: Kotlin Sort Object List with Kotlin Selector function – crossinline selector: (T) -> R?

3. Binary Search with Comparison function

We use below method signature for Binary Search with Comparison function:

public fun  List.binarySearch(fromIndex: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int

So We define an appropriate Comparison function as below:

fun comparison(p1: Product, p2: Product): Int = (p1.price - p2.price).toInt()

Binary Search with Comparison function will search in the ascending sorted list or its range for an element for which [comparison] function returns zero 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 by [comparison] function. Otherwise, the result is undefined.

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(: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int
val index = sortedProducts.binarySearch{comparison(it, Product(price = 284.93))}
			// -> simple representation solution
			// sortedProducts.binarySearch{(it.price - 284.93).toInt()}

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(0, 3, {comparison(it, Product(price = 284.93))})
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(3, sortedProducts.size, {comparison(it, Product(price = 284.93))})
println("index3 = $index3"); // index3 = -4	

III. Full Sourcecode

package com.javasampleapproach.binarysearch

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

fun selector(p: Product): Double = p.price
fun comparison(p1: Product, p2: Product): Int = (p1.price - p2.price).toInt() 

fun main(args : Array){
	
	/*
 	 * //////////////////////
 	 * I. Initial Data
  	 * //////////////////////
     */
	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))
	
	/*
 	 * //////////////////////
 	 * II. Sorting Data
  	 * //////////////////////
     */	
	// Use sortedBy() method signature as below:
	// -> public inline fun > Iterable.sortedBy(crossinline selector: (T) -> R?): List
	val sortedProducts = products.sortedBy({selector(it)})
						// -> simple representation solution
						// val sortedProducts = products.sortedBy{it.price}
	println("=====================Sorted Products=====================")
	sortedProducts.forEach{println(it)}
	// 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)
	*/
	
	
	/*
 	 * //////////////////////
 	 * III. Binary Search
  	 * //////////////////////
     */	
	println("\n=====================Do Binary Search=====================")
 	//	Use binarySearch() method signature as below: 
 	//	-> public fun  List.binarySearch(: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int
	val index = sortedProducts.binarySearch{comparison(it, Product(price = 284.93))}
	            // -> simple representation solution
	            // sortedProducts.binarySearch{(it.price - 284.93).toInt()}
	
	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(0, 3, {comparison(it, Product(price = 284.93))})
	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(3, sortedProducts.size, {comparison(it, Product(price = 284.93))})
	println("index3 = $index3"); // index3 = -4	
}


By grokonez | December 16, 2017.


Related Posts


2 thoughts on “Kotlin Binary Search for Object List with Comparison function – comparison: (T) -> Int”

Got Something To Say:

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

*