Binary Search in Go: 4 Variants You Need To Know

Binary Search falls into the category of Interval Search which is a type of algorithms for searching through sorted arrays or lists of elements… There is more to algorithms than just their classification. One way to solidify your understanding of Data Structures and Algorithms is to study their variations. In this blog post, I provide an overview of the different variations of Binary Search in Go. You’ll notice that it starts off easy but increases in difficulty as we look into more use cases and variations.

What is Binary Search and How Does it Work?

Binary search is one of the most widely used algorithms out there due to its efficiency. It works on a sorted list/slice of elements.

The first version we’ll look into is the classic implementation, repeatedly dividing the search interval (search space) until we find the target element. That’s why Binary Search is called a “divide and conquer” algorithm.

Basically, the steps that need to be performed repeatedly (until the target is found or the list is exhausted) are as follows:

1. Compare the target with the middle element.

2. If they are equal, return some value. Be it the key, the index, or even the closest index.

3. If the target is less than the element, search the left half.

4. If the target is greater, search the right half.

Note: The last two steps take advantage of the fact that the elements are sorted in an ascending order ( i.e. ascending search space.)

The return value in the second step can determine the version/variant of the algorithm. This will become clear with the four fundamental variants below.

Variations based on finding specific elements

Variant 1 - Binary Search Contains

Use this variant of Binary Search if all you need to find out is whether the target element exists in the slice or not. The value that needs to be returned in the second step is a Boolean. Either true or false. Simple as that.

func binarySearchContains(arr []int, target int) bool {

    low, high := 0, len(arr)-1

    for low <= high {
        mid := low + (high-low)/2
        if arr[mid] == target {
            return true // Found!
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return false // Target not found

}

func main() {

    sortedSlice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    target := 7

    if binarySearchContains(sortedSlice, target) {
        fmt.Printf("%d is in the slice!\n", target)
    } else {

        fmt.Printf("%d is not in the slice.\n", target)

    }

}

Output:

7 is in the slice!

Variant 2 - Binary Search First Occurrence

Use this variant of Binary Search if you need to find the index of the first occurrence. Sometimes the slice contains multiple occurrences of the search target. Thing is, we’re looking for a target which we may find in the middle. Once/if it is found we still have to look to the left of it because the found element may be not the first occurrence.

func firstOccurrence(slice []int, target int) int {
leftmost, rightmost := 0, len(slice)-1

occ := -1

for leftmost <= rightmost {
    mid := leftmost + (rightmost-leftmost)/2
    if slice[mid] == target {
        occ = mid
        rightmost = mid - 1
    } else if slice[mid] < target {
    leftmost = mid + 1
    } else {
        rightmost = mid - 1
    }
}

return occ // Target not in the slice

}

func main() {
    sortedSlice := []int{1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 10}

    target := 5

    index := firstOccurrence(sortedSlice, target)

    if index != -1 {
        fmt.Printf("Fisrt occurrence of %d is at index %d\n", target, index)
    } else {
        fmt.Printf("%d is not in the slice.\n", target)
    }

}

Output

Fisrt occurrence of 5 is at index 4

Explanation

• Initial Match:

  • When mid initially matches the target at index 5 (value 5), we update occ (our result tracker) to store this index.

• Continuation for the Leftmost Occurrence:

  • Unlike standard binary search, we don’t stop at the initial match. Instead, we set rightmost to mid - 1 to narrow down the search space to the left side, ensuring we find the first occurrence of the target.

• Iterative Search for Leftmost Occurrence:

  • The algorithm iteratively continues the search in the narrowed-down left segment of the array. This involves updating leftmost to mid + 1 during each iteration.

• Repeating the Process:

  • The process repeats until leftmost is no longer less than or equal to rightmost, indicating that the entire left side has been explored.

• Result:

  • The final result, stored in occ, holds the index of the leftmost occurrence of the target in the sorted slice.

Variant 3 - Binary Search Last Occurrence

This is just like the last variant except instead of looking at the left half to find the first occurrence we look at the right in order to find the last occurrence.

func lastOccurrence(slice []int, target int) int {
leftmost, rightmost := 0, len(slice)-1

occ := -1

for leftmost <= rightmost {
    mid := leftmost + (rightmost-leftmost)/2
    if slice[mid] == target {
        occ = mid
        leftmost = mid + 1 // Move to the right side to find last occurrence
    } else if slice[mid] < target {
    leftmost = mid + 1
    } else {
        rightmost = mid - 1
    }
}
return occ // Target not in the slice

}

func main() {

    sortedSlice := []int{1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 10}

    target := 5

    index := lastOccurrence(sortedSlice, target)

    if index != -1 {
        fmt.Printf("Last occurrence of %d is at index %d\n", target, index)
    } else {
        fmt.Printf("%d is not in the slice.\n", target)
    }

}

Output

Last occurrence of 5 is at index 6

Explanation

• When mid initially matches the target at index 5 (value 5), we update occ (our result tracker) to store this index.

• Diverging from the standard binary search, we set leftmost to mid + 1 instead of rightmost during the initial match. This ensures we explore the right side of the array for the last occurrence.

• The algorithm iteratively continues the search in the narrowed-down right segment of the array, involving updates to leftmost and rightmost.

• The process repeats until leftmost is no longer less than or equal to rightmost, indicating that the entire right side has been explored.

• The final result, stored in occ, now holds the index of the rightmost occurrence of the target in the sorted slice.

Variant 4 - Binary Search Closest Element

Use this variation to find the element that is the closest to the target value. This is particularly useful when we have a sorted slice and the target we’re looking for is not found in the slice. And so, we get the one element in the slice that is closest to it in value.

func closestElement(slice []int, target int) int {

    l, r := 0, len(slice)-1

    closestIndex := 0 // Placeholder



    for l <= r {

        mid := l + (r-l)/2

        if slice[mid] == target {
            return mid // Exact match found, return target
        }

        diff := int(math.Abs(float64(slice[mid] - target)))

        if closestIndex == 0 || diff < int(math.Abs(float64(closestIndex-target))) {
            closestIndex = mid
        }

        if slice[mid] < target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return closestIndex
}

func main() {
    sortedSlice := []int{1, 2, 3, 4, 5, 7, 8, 9, 10}

    target := 6

    closestId := closestElement(sortedSlice, target)

    fmt.Printf("The closest element to %d is %d at index %d\n", target, sortedSlice[closestId], closestId)
}

Output

The closest element to 6 is 7 at index 5

Explanation

• Initialization:

  • l is initially set to 0 (index of the first element in the slice).

  • r is set to len(arr) - 1 (index of the last element in the array).

  • closestIndex is initialized to 0.

• Binary Search:

  • The algorithm follows a standard binary search approach to find the target or the closest element.

  • At each iteration, the middle index mid is calculated, and the difference between the value at mid and the target is computed in order to determine the proximity.

  • If the current element at mid is closer to the target than the current closestIndex element, update closestIndex to the mid index.

  • The search space is adjusted based on whether the current element is less than or greater than the target, following the binary search paradigm.

  • The process repeats until the search space is exhausted (l is no longer less than or equal to r).

  • The function returns the closestIndex, representing the index of the element in the slice that is closest to the target.

These are just a few variants of the Binary Search algorithm and there are many others. It suffices to know that even the simplest algorithms can serve a wide variety of purposes. Keeping that mind enables us as developers to adapt our thinking and not just perceive algorithms as ready-made recipes for a limited set of scenarios. The sky is the limit basically. For me it’s a fun way of thinking about all the variations and the combination of steps that can be integrated into a well-known algorithm. It’s a powerful tool to solve a diverse set of challenges.

I hope this post gave you a useful overview of the diverse implementations of binary search variants in Golang. Stay tuned for more on other subjects related to Golang and Data Structures.

Check out the full code for the algorithms with tests on GitHub. Feel free to clone the repository, run the tests, and even contribute your improvements. Your feedback is always appreciated!