# binarySearch() with suspending comparison function?

**URL:** <https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193>\
**Category:** Support\
**Created:** [June 23, 2021, 2:52pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193 "2021-06-23T14:52:16Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![nottheoilrig](https://avatars.discourse-cdn.com/v4/letter/n/f9ae1b/32.png) [@nottheoilrig](https://discuss.kotlinlang.org/u/nottheoilrig)\
**Post date:** [June 23, 2021, 2:52pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/1 "2021-06-23T14:52:16Z")

</div>

How do I do a [binary search](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/binary-search.html#:~:text=the%20given%20comparison%20function%20returns%20zero%20using%20the%20binary%20search%20algorithm.) with a suspending comparison function? e.g.

```kotlin
suspend fun main() {
  // ...
  // Find the minimum input in a..b such that the balance is zero
  (a..b).toList().binarySearch { contributionsYouAreDeducting ->
    // error: suspension functions can be called only within coroutine body
    val newForm = coroutineScope { evalForm(contributionsYouAreDeducting, this) }
    // ^
    if (newForm.yourReturn.balance() > 0) -1 else 1
  }
}

```

Replacing `coroutineScope()` with [`runBlocking()`](https://kotlin.github.io/kotlinx.coroutines/kotlinx-coroutines-core/kotlinx.coroutines/run-blocking.html) disappears the error, however I suspect this approach has problems? i.e.

```kotlin
suspend fun main() {
  // ...
  (a..b).toList().binarySearch { contributionsYouAreDeducting ->
    val newForm = runBlocking { evalForm(contributionsYouAreDeducting, this) }
    if (newForm.yourReturn.balance() > 0) -1 else 1
  }
}
```

---

<div class="post-metadata">

**Author:** ![broot](https://avatars.discourse-cdn.com/v4/letter/b/a88e57/32.png) [@broot](https://discuss.kotlinlang.org/u/broot)\
**Post date:** [June 23, 2021, 3:08pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/2 "2021-06-23T15:08:25Z")

</div>

Why do you need to do this in the first place? Do you need to perform a parallel computing in `evalForm()`? In that case using `runBlocking()` or your own coroutine scope does not sound like a bad idea.

Also, remember that you can use `binarySearch()` only on already sorted lists.

Also2, if this is what you need to do:

> Find the minimum input in a…b such that the balance is zero

Then I don’t really see how `binarySearch()` can help you here. Why won’t you just iterate from a to b and finish when you get 0?

---

<div class="post-metadata">

**Author:** ![nottheoilrig](https://avatars.discourse-cdn.com/v4/letter/n/f9ae1b/32.png) [@nottheoilrig](https://discuss.kotlinlang.org/u/nottheoilrig)\
**Post date:** [June 23, 2021, 5:15pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/3 "2021-06-23T17:15:49Z")

</div>

> [@broot](#):
>
> Why do you need to do this in the first place? Do you need to perform a parallel computing in `evalForm()` ?

Yup, exactly.

> [@broot](#):
>
> In that case using `runBlocking()` or your own coroutine scope does not sound like a bad idea.

Thanks for your help! I don’t understand though: what do you mean by your own coroutine scope?

> [@broot](#):
>
> Also, remember that you can use `binarySearch()` only on already sorted lists.

The balance is monotonic (it’s [piecewise linear](https://en.wikipedia.org/wiki/Piecewise_linear_function#:~:text=In%20mathematics%20and%20statistics%2C%20a,composed%20of%20straight%2Dline%20segments.) and monotonic). You’re right, that’s significant.

> [@broot](#):
>
> Why won’t you just iterate from a to b and finish when you get 0?

The comparison function (`evalForm().yourReturn.balance()`) is expensive, so unfortunately iteration isn’t feasible.

---

<div class="post-metadata">

**Author:** ![broot](https://avatars.discourse-cdn.com/v4/letter/b/a88e57/32.png) [@broot](https://discuss.kotlinlang.org/u/broot)\
**Post date:** [June 23, 2021, 6:46pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/4 "2021-06-23T18:46:22Z")

</div>

> [@nottheoilrig](#):
>
> what do you mean by your own coroutine scope?

I meant [CoroutineScope](https://kotlin.github.io/kotlinx.coroutines/kotlinx-coroutines-core/kotlinx.coroutines/-coroutine-scope/), but on the second thought I’m not sure if it makes any sense here.

Note that by default `runBlocking()` dispatches coroutines in a single thread that invoked it, so it won’t improve the performance. You need to switch to `Dispatchers.Default` (it uses a shared thread pool for CPU-intensive tasks) or create your own thread pool. You can switch the dispatcher by e.g. `runBlocking(Dispatchers.Default) { ... }`.

> [@nottheoilrig](#):
>
> The balance is monotonic

Ahh, ok, that explains everything. I must say this solution is pretty clever. I mean especially that your comparison function never returns 0, so it always finds the first item with balance=0. I really like it.

---

<div class="post-metadata">

**Author:** ![broot](https://avatars.discourse-cdn.com/v4/letter/b/a88e57/32.png) [@broot](https://discuss.kotlinlang.org/u/broot)\
**Post date:** [June 23, 2021, 7:46pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/5 "2021-06-23T19:46:28Z")

</div>

> [@broot](#):
>
> on the second thought

On third thought… ok, I give up, we probably need to wait for someone who is more experienced with coroutines. Your `main()` is marked with `suspend`, so if this is an entry point to the application then I think this is ok. Main thread will be blocked, no problem here.

My concern is what if we need to use `binarySearch()` or similar function from any suspend function, so potentially from any coroutine or dispatcher. For example, if we do it from the coroutine running with `Dispatchers.Default`, we will block one of its threads which we should avoid. I created a simple test:

```auto
newFixedThreadPoolContext(2, "my-pool").use { ctx ->
    runBlocking(ctx) {
        runBlocking(ctx) {
            launch {
                println("1: ${Thread.currentThread().name}")
                Thread.sleep(1000)
            }
            launch {
                println("2: ${Thread.currentThread().name}")
                Thread.sleep(1000)
            }
        }
    }
}

```

First `runBlocking()` blocks the main thread, second `runBlocking()` blocks one of two threads in our pool. so both subtasks runs sequentially, not concurrently. If we add a third `runBlocking()`, it will be a deadlock.

So I don’t really know, how to properly handle such cases in general. I mean cases where we are in suspendable/coroutine context and we need to get through unsuspendable code to get to another suspend function.

I wonder if it would be technically possible for `runBlocking()` to recognize that it was invoked from the thread that is managed by one of coroutine dispatchers and in that case it would temporarily return the thread to the pool. It does not sound easy, but possible (?). Anyway, it doesn’t seem to do it already, as can be seen in my example.

---

<div class="post-metadata">

**Author:** ![nottheoilrig](https://avatars.discourse-cdn.com/v4/letter/n/f9ae1b/32.png) [@nottheoilrig](https://discuss.kotlinlang.org/u/nottheoilrig)\
**Post date:** [June 23, 2021, 9:38pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/6 "2021-06-23T21:38:54Z")

</div>

> [@broot](#):
>
> cases where we are in suspendable/coroutine context and we need to get through unsuspendable code to get to another suspend function.

🎯 That’s what I’m after. Thanks for explaining the problem with `runBlocking()`, hopefully someone knows how to do it properly, or is there an existing issue/discussion?

---

<div class="post-metadata">

**Author:** ![mtimmerm](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/mtimmerm/32/7160_2.png) [@mtimmerm](https://discuss.kotlinlang.org/u/mtimmerm)\
**Post date:** [June 25, 2021, 4:48am UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/7 "2021-06-25T04:48:51Z")

</div>

This is a good example of the red/blue function problem: [What Color is Your Function? – journal.stuffwithstuff.com](http://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/)

The bottom line is that you need a suspending version of binarySearch. The standard library doesn’t provide one, so you’ll have to write your own. It’s not hard:

```auto
while(a<b) {
    val test = a+(b-a)/2
    val newForm = evalForm(test, this)
    if (newForm.yourReturn.balance() > 0) {
        a = test+1
    } else {
        b = test
    }
}

```

---

<div class="post-metadata">

**Author:** ![broot](https://avatars.discourse-cdn.com/v4/letter/b/a88e57/32.png) [@broot](https://discuss.kotlinlang.org/u/broot)\
**Post date:** [June 25, 2021, 7:18am UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/8 "2021-06-25T07:18:03Z")

</div>

> [@mtimmerm](#):
>
> This is a good example of the red/blue function problem

I think this is similar, but not the same. Note that suspending functions are actually synchronous, so we are all in blue here.

Synchronous and asynchronous operations are somewhat incompatible even conceptually, so whatever tools we will create, the problem will remain. I believe the problem with coroutines is strictly technical, it is related to how they were implemented, so maybe there is a room for improvement here.

But the conclusion is probably right: the best we can do is to replace the library or utility function with one that supports suspending.

---

<div class="post-metadata">

**Author:** ![nottheoilrig](https://avatars.discourse-cdn.com/v4/letter/n/f9ae1b/32.png) [@nottheoilrig](https://discuss.kotlinlang.org/u/nottheoilrig)\
**Post date:** [June 25, 2021, 6:57pm UTC](https://discuss.kotlinlang.org/t/binarysearch-with-suspending-comparison-function/22193/9 "2021-06-25T18:57:45Z")

</div>

Thanks for your help! I found [an existing YT](https://youtrack.jetbrains.com/issue/KT-17192) for the higher order + suspending function problem [and added mention of the `binarySearch()` case to it](https://youtrack.jetbrains.com/issue/KT-17192#focus=Comments-27-4991195.0-0).

It sounds like `inline` would fix the `binarySearch()` case? In the absence of [suspending overloads](https://youtrack.jetbrains.com/issue/KT-17846) …