## DEV Community

Phil Tenteromano for Vets Who Code

Posted on • Updated on

# 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💪🧵!

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.