Introduction

In recent days, I have been refreshing my knowledge by having some fun solving problems in leetcode and this post marks the start of a series of posts related to general algorithmic challenges I may encounter and find interesting to share. This article presents details about three leetcode algorithm problems that were resolved using a Binary Search approach and implemented in Golang.

What is a Binary Search?

Binary Search is a search algorithm with complexity O(log n) that accepts as input a sorted list and a target number, and recursively finds the middle element of the list until the target number is located.

A key requirement here is the fact that for the Binary Search algorithm to work, the input list must be sorted. In a scenario we have an unsorted list as input, our task would be to first sort it, at a cost of added complexity to the runtime, O( nlog n) if using a sorting algorithm such as MergeSort.

Although the Binary Search algorithm is deemed a recursive algorithm, we can use both iterative and recursive approaches in its implementation. For that reason, the three problems presented in this article provide both iterative and recursive solutions.

Implementation Details

All three problems presented share one requirement: we must solve them with O(log n) runtime complexity.

Iterative approach: At every iteration, the search space is reduced by half by using the middle element as a divisor to identify whether the target number is in the first or second half of the list. We repeat the process the target number is found.

Recursive approach: The recursive iteration uses no loop and the recursive calls drive the reduction of the search space. At every recursive call, we passed the full list along with the left and right index pointers for the reduction of the search space in the list.

I took special consideration on problem #3. Given the target number may not exist in the list on this problem, the extremes of the list must be evaluated. If we reach a point in which the pivot (middle) index is 0 or len(list) - 1, we must return the value of the pivot at that position to avoid out of boundaries exceptions.

Binary Search – Problem #1

Problem:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Leet code link here.

GitHub solution link here.

Implementation

package main

import "fmt"

func main() {
	nums := []int{-1, 0, 3, 5, 9, 12}
	target := 9

	fmt.Println(search(nums, target))
	fmt.Println(searchRecursive(nums, target))

}

// iterative approach
func search(nums []int, target int) int {
	left := 0
	right := len(nums) - 1

	for {
		if left > right {
			break
		}
		pivot := left + (right-left)/2
		value := nums[pivot]

		if value == target {
			return pivot
		} else if value > target {
			right = pivot - 1
		} else {
			left = pivot + 1
		}
	}

	return -1
}

// recursive approach
func searchRecursive(nums []int, target int) int {

	return (recursive(nums, target, 0, len(nums)-1))
}

func recursive(nums []int, target int, left int, right int) int {

	pivot := left + (right-left)/2

	if left > right {
		return -1
	}

	if nums[pivot] == target {
		return pivot
	} else if nums[pivot] < target {
		return recursive(nums, target, pivot+1, right)
	} else {
		return recursive(nums, target, left, pivot-1)
	}
}

Binary Search – Problem #2

Problem:

Leet code link here.

GitHub solution link here.

Implementation

package main

import "fmt"

var testCases map[string]int
var currentTest string
var expectedResult string

func main() {
	testCases = make(map[string]int)
	testCases["t1"] = 5
	testCases["r1"] = 4

	testCases["t2"] = 1
	testCases["r2"] = 1

	currentTest = "t1"
	expectedResult = "r1"

	input := testCases[currentTest]

	fmt.Println("--- Recursive Approach ---")
	result := firstBadVersionRecursive(input)
	if result == testCases[expectedResult] {
		fmt.Printf("Correct. Output: %d. Expected: %d.\n", result, testCases[expectedResult])
	} else {
		fmt.Printf("Failed. Output: %d. Expected: %d.\n", result, testCases[expectedResult])
	}

	fmt.Println("--- Iterative Approach ---")
	result = firstBadVersion(input)
	if result == testCases[expectedResult] {
		fmt.Printf("Correct. Output: %d. Expected: %d.\n", result, testCases[expectedResult])
	} else {
		fmt.Printf("Failed. Output: %d. Expected: %d.\n", result, testCases[expectedResult])
	}

}

func firstBadVersionRecursive(input int) int {
	return (recursive(input, 0, input-1))
}

func recursive(input int, left int, right int) int {

	for i := 0; i <= input; i++ {

		middle := left + (right-left)/2

		if isBadVersion(middle) {

			if isBadVersion(middle - 1) {
				return recursive(input, left, middle-1)
			}
			return middle
		} else {
			left = middle + 1
			continue
		}
	}

	return -1
}

func firstBadVersion(n int) int {

	left := 0
	right := n
	firstBad := 0

	for i := 0; i <= n; i++ {

		pivot := left + (right-left)/2

		isBad := isBadVersion(pivot)

		if isBad {
			if !isBadVersion(pivot - 1) {
				firstBad = pivot
				break
			} else {
				right = pivot - 1
				continue
			}
		} else {
			left = pivot + 1
		}
	}

	return firstBad
}

func isBadVersion(version int) bool {

	bad := testCases[expectedResult]
	if version >= bad {
		return true
	} else {
		return false
	}
}

Binary Search – Problem #3

Problem:

Leet code link here.

GitHub solution link here.

Implementation

package main

import "fmt"

var input []int
var target int
var output int

func main() {

	input = []int{1, 3}
	target = 2
	output = 0

	fmt.Println(searchInsertIterative(input, target))
	fmt.Println(recursiveCall(input, target))
}

func searchInsertIterative(nums []int, target int) int {

	left := 0
	right := len(nums) - 1

	for true {
		middle := left + (right-left)/2

		value := nums[middle]

		if target == value {
			return middle
		} else if value > target {
			if middle == 0 {
				return 0 // It should be inserted at the last position
			} else if nums[middle-1] > target {
				right = middle - 1
			} else if nums[middle-1] < target {
				return middle
			} else { // is equal
				return middle - 1
			}
		} else {
			if middle == len(nums)-1 {
				return len(nums)
			} else if nums[middle+1] > target {
				return middle + 1
			} else if nums[middle+1] < target {
				left = middle + 1
			} else { // is equal
				return middle + 1
			}
		}
	}

	return 0

}

func recursiveCall(nums []int, target int) int {
	return searchRecursive(input, target, 0, len(input)-1)
}

func searchRecursive(nums []int, target int, left int, right int) int {

	middle := left + (right-left)/2

	value := nums[middle]

	if target == value {
		return middle
	} else if value > target {

		if middle == 0 {
			return 0
		}

		if nums[middle-1] > target {
			right = middle - 1
			return searchRecursive(nums, target, left, right)
		} else if nums[middle-1] < target {
			return middle
		} else {
			return middle - 1
		}
	} else {

		if middle == len(nums)-1 {
			return len(nums)
		}
		if nums[middle+1] > target {
			return middle + 1
		} else if nums[middle+1] < target {
			left = middle + 1
			return searchRecursive(nums, target, left, right)
		} else {
			return middle + 1
		}
	}
}

Conclusion

This article briefly explained how the Binary Search Algorithm works, focusing on presenting a few problems from leetcode in which the binary search approach was required.

Remember, the binary search algorithm requires an ordered list as input so that the search can proceed with a complexity O(log n). If you are looking for a refresher on understanding the Big O notation O(log n), look no further than this video by Kantan Coding.

Until next time!