Kotlin Binary Search for Object List with Selector function – crossinline selector: (T) -> K?

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 Selector function – selector: (T) -> R?.

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 Comparison function – comparison: (T) -> Int

I. Technologies

– Kotlin 1.1.61
– Java 8

II. Kotlin Binary Search with Selector function

Step to do:
– Create data model
– Create Selector function
– Create a sorted list
– Binary Search with Selector 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 Selector function

We need define a selector function selector: (T) -> R?:

fun selector(p: Product): Double = p.price
3. 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

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?

4. Binary Search with Selector function

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

public inline fun > List.binarySearchBy(key: K?, fromIndex: Int = 0, toIndex: Int = size, crossinline selector: (T) -> K?): Int

Binary Search with Selector function will search in the ascending sorted list or its range for an element having the key returned by the specified [selector] function equal to the provided [key]. It will return the index of find out element. Otherwise, it will return the inverted insertion point (-insertion point – 1).

Note: The list is expected to be sorted into ascending order by the Comparable natural ordering of keys of its elements.

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

//	Use binarySearchBy() method signature as below: 
//	-> public inline fun > List.binarySearchBy(key: K?, fromIndex: Int = 0, toIndex: Int = size, crossinline selector: (T) -> K?): Int
val index = sortedProducts.binarySearchBy(key=284.93, selector={selector(it)})
            // -> simple representation solution
            // val index = sortedProducts.binarySearchBy(key=284.93, selector={it.price})

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.binarySearchBy(284.93, 0, 3, {selector(it)})
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.binarySearchBy(284.93, fromIndex=3, selector={selector(it)})
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 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 binarySearchBy() method signature as below: 
	//	-> public inline fun > List.binarySearchBy(key: K?, fromIndex: Int = 0, toIndex: Int = size, crossinline selector: (T) -> K?): Int
	val index = sortedProducts.binarySearchBy(key=284.93, selector={selector(it)})
	            // -> simple representation solution
	            // val index = sortedProducts.binarySearchBy(key=284.93, selector={it.price})
	
	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.binarySearchBy(284.93, 0, 3, {selector(it)})
	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.binarySearchBy(284.93, fromIndex=3, selector={selector(it)})
	println("index3 = $index3"); // index3 = -4
}


By grokonez | December 16, 2017.


Related Posts


Got Something To Say:

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

*