3
\$\begingroup\$

I'm aware that a function in the standard library exists. Please give me feedback regarding good coding conventions and standards.

fun main(arg: Array<String>) {
    val intList = listOf<Int>(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    println("Enter a valid number:")
    val x = readLine()!!.toIntOrNull() ?: run {
        println("You didn't type a valid number.")
        return
    }
    binarySearch(intList, x)
}

fun binarySearch(list: List<Int>, searchItem: Int){
    val mid = list.size / 2
    val isInFirstHalf =
                list
                    .take(mid)
                    .any { it == searchItem }
    do {
        val result =
                if (isInFirstHalf)
                    list.slice(0 until mid)
                else
                    list.slice(mid until list.size)
        println(result.joinToString())
        if (result.size == 1) break
        binarySearch(result, searchItem)
        return
    } while (true)
    println("Binary search found $searchItem.")
}
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Vogel612
    Commented Aug 11, 2017 at 13:05

2 Answers 2

3
\$\begingroup\$
  • Instead of parsing an Int with the catch (e: NumberFormatException) { ... }, consider using the String.toIntOrNull() extension:

    val x = readLine().toIntOrNull() ?: run {
        println("You didn't type a valid number.")
        return
    }
    
  • In Kotlin extension functions, reference the members of the receiver type without explicit this: this.sizesize unless the name is ambigous.

  • Instead of (0 until this.size / 2).map { this.elementAt(it) }, you could just use take(size / 2) (but see below why you should not).

  • The approach you take to check in which half the item can be located and move the binary search window to a half of the list (by copying or removing the first half) changes the run time of the algorithm significantly: while binary search should take \$ O(log n) \$ time to find an element, your implementation additionally performs \$ O(n/2 + n/4 + n/8 + ...) = O(n) \$ operations checking the first half and then copying or removing the items, making the search asymptotically as slow as serial search through the list. Consider checking only the item in the middle of the list (the assumption that the list is sorted allows you to do that) and then using .subList(...) to get a view of a portion of the original list, in \$ O(1) \$ time.

\$\endgroup\$
1
\$\begingroup\$

binarySearch is completely unreadable. If I was grading this I would fail you even if your code works. Readability is everything for software development. (Sorry for being harsh.)

As already pointed out, doing binary search by removal is not a good idea from a performance point of view. And if you want to do that, you should probably use immutable lists throughout as this the recommended practice in Kotlin. So instead of removing a half in place, you return a new list made of the other half. But is still much less efficient than just traversing the list without deleting/creating anything as is usually done in binary search.

Naming variables and functions is a big part of readability. binarySearch is a misleading misnomer here. You should wrap the do-while loop in a function called binarySearch and change the name of the current one to something like selectHalf (but you find a better name).

You seem to like fitting everything in one line, but this is bad practice. For example, this.size / 2 until this.size).map { this.elementAt(it) }.forEach { this.remove(it) } is more readable as

(this.size / 2 until this.size)
            .map { this.elementAt(it) }
            .forEach { this.remove(it) }

You should not put complicated code in an if-clause, so instead of if ((0 until this.size / 2).map { this.elementAt(it) }.any { it == item }) {...}:

val isInFirstHalf = (0 until this.size / 2)
        .map { this.elementAt(it) }
        .any { it == item })
if (isInFirstHalf) { ... }

Running over the indices in the style (0 until this.size / 2).map { this.elementAt(it) }... is so awkward to read that using a for-loop would be more appropriate.

But actually for the two tasks where you are doing that (1. checking if item is present in the first half and 2. return one half), there are simpler functions: list.take(mid).any { it == item} and list.slice(0..mid)) where mid = list.size / 2. As I wrote at the beginning, this returns a slice instead of removing some part, which allows us to use immutable lists everywhere. You should always take a good look at all the methods that exist in the collections since there might be one doing exactly what you want.

\$\endgroup\$
1
  • \$\begingroup\$ I used .remove because I couldn't figure out how to do exactly what you were suggesting. I'll try using slice. cheers \$\endgroup\$ Commented Aug 11, 2017 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.