Concurrency in Golang with a Binary Search Problem

Problem

Solving problems with Go can be a really fun and rewarding experience. In this post, I'll go through a "medium" Leetcode challenge "Find First and Last Position of Element in Sorted Array".

The problem is fairly straight forward - it's a sorted array, so we know we can use Binary Search. However, the array is non-decreasing, meaning that elements are allowed to repeat. We're given the task to return a size-2 array with the start and ending index of where the targeted element exists in the array.

Here is the prompt:

Solution Steps

Try to think of a mental solution for yourself before reading any further.

Ignoring the trivial linear solution, we'll focus on the Binary Search solution. Let's think of the steps:

1. Binary Search for the target
2. Split the array into "lower" and "upper"
3. Binary Search on both, separately
4. Repeat until both splits no longer find the target

Pretty straight forward, I had a lot of fun solving it with Go - most of the syntax is similar to other languages. One of Go's most important features is how simple it makes Concurrency and multi-threading. It uses a data type called Channels with its native Goroutine to synchronize data across threads. Think of it as async / await in other languages.

Code

We'll make a simple Binary Search method, with runtime of O(log n):

// BinarySearch method
func findTarget(nums []int, target int) int {
    low, high := 0, len(nums) - 1

    for low <= high {
        mid := (high + low) / 2

        if nums[mid] == target {
            return mid
        }

        if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return -1
}

We'll call this method a few times, but on ever-decreasing slices of the array - we'll never call it with the same memory space twice.

Now we can easily find any initial target:

func searchRange(nums []int, target int) []int {
    // Initial Search
    high := findTarget(nums, target)

    // Didn't find it, return early
    if high == -1 {
        return []int{-1, -1}
    }
    // TODO: finish function
}

Here we have the early return, when the target does not exist at all. But now what happens when we find it? Well we need to search up and down the array. We can of course do this linearly, but think about the worst case: what if theres an array of 10 million elements, all target. If we started with the center - now we have to linearly crawl through 5 million elements up and down the array. Not great!

Because of that, we'll stick with Binary Search. Golang allows us to cut up its slice datatype (slices are pretty much arrays, with a lot more flexibility, read more here). Without using concurrency, here's the rest of the method:

func searchRange(nums []int, target int) []int {
// ...

// Found target, lets search left and right
    low := high

    // Search lower half of array
    for {
        temp := findTarget(nums[:low], target)
        if temp == -1 {
            break
        }
        low = temp
    }

    // Search upper half of array
    for {        
        temp := findTarget(nums[high + 1:], target)
        if temp == -1 {
            break
        }
        // temp is reindexed at 0 - account for that
        high += temp + 1
    }

    return []int{low, high}
}

Pretty straight forward, we're just binary searching until we no longer find the element on each slice. Great! This passes on Leetcode, and we can be done. But how can we make this a little better? A primary bottleneck with this code is the fact that the "Upper" search is completely blocked until the "Lower" search completes.

We have an opportunity here - the two for loops are acting on completely separate memory addresses. Let's see what we can do with Goroutines and a Channel, here's the entire completed function, with added concurrency:

func searchRange(nums []int, target int) []int {
    // Initial Search
    high := findTarget(nums, target)

    // Didn't find it, return early
    if high == -1 {
        return []int{-1, -1}
    }

    // Hold our data from the threads
    bounds := make(chan int, 2)

    // Search lower half of array, in its own thread (goroutine)
    go func(low int) {
        for {
            temp := findTarget(nums[:low], target)
            if temp == -1 {
                break
            }
            low = temp
        } 
        // Shovel the lower-bound into the Channel
        bounds<-low
    }(high)

    // Search upper half of array, in its own thread (goroutine)
    go func(high int) {
        for {
            temp := findTarget(nums[high + 1:], target)
            if temp == -1 {
                break
            }
            high += temp + 1
        }
        // Shovel the upper-bound into the Channel
        bounds<-high
    }(high)

    newLow := <-bounds
    newHigh := <-bounds

    // No garauntee which one finishes first, so order them
    if newLow > newHigh {
        newLow, newHigh = newHigh, newLow
    }

    return []int{newLow, newHigh}
}

Now, we create an anonymous function and call it immediately, but we use the go keyword to run a Goroutine. With the scope of the bounds Channel, we can shovel data in and out of it. When pulling data out of the Channel (<-bounds), Go will block until there is actually data there.

This means that both the "lower" and "upper" slices will be processed simultaneously! Congratulations, you just solved a Leetcode challenge using thread-safe concurrency💪🧵!

Follow up

We can also clean this code up a bit by pulling the functions for "lower" and "upper" out into their own methods. This would make the primary searchRange method a bit cleaner. But for the sake of simplicity, I left them in.

Comments

[Victor Ray]

Awesome.

[birowo]

gitlab.com/birowo/search-range

[Sebastian Lopez]

Nice example, but bear in mind that concurrency can have a negative impact on complexity and performance because of synchronization, resource allocation, etc. Always benchmark your code :) In my tests, the solution without concurrency runs 5x~12x faster depending on the input size.

[Phil Tenteromano]

Yes, mostly this is just a soft introductory example of Go's concurrency model on a well known problem (binary search). Not meant to be a performance optimization solution.