Golang Binary Search Algorithm

1. Introduction

Binary Search is a popular search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array, eliminating half of the remaining elements based on the comparison, and continues to do this until the target value is found or until there are no more elements left to search. This approach is much more efficient than linear search, especially for large datasets, as it has a time complexity of O(log n).

2. Implementation Steps

1. Determine the middle element of the array.

2. If the middle element matches the target value, return its index.

3. If the middle element is greater than the target value, repeat the search process with the left half of the array.

4. If the middle element is less than the target value, repeat the search process with the right half of the array.

5. If the array does not contain the target value, return -1.

3. Implementation in Golang

package main
import (
	"fmt"
)
// binarySearch function returns the index of the element if found, else returns -1
func binarySearch(arr []int, l int, r int, x int) int {
	if r >= l {
		mid := l + (r-l)/2
		// If the element is present at the middle itself
		if arr[mid] == x {
			return mid
		}
		// If the element is smaller than mid, search in the left sub-array
		if arr[mid] > x {
			return binarySearch(arr, l, mid-1, x)
		}
		// Else, search in the right sub-array
		return binarySearch(arr, mid+1, r, x)
	}
	// If the element is not present in the array
	return -1
}
func main() {
	data := []int{10, 20, 30, 40, 50, 60, 70, 80, 90}
	searchNum := 70
	index := binarySearch(data, 0, len(data)-1, searchNum)
	if index != -1 {
		fmt.Printf("Element %d is present at index %d.\n", searchNum, index)
	} else {
		fmt.Printf("Element %d is not present in the array.\n", searchNum)
	}
}

Output:

Element 70 is present at index 6.

Explanation:

1. The binarySearch function takes an array, left and right boundaries of the section of the array to be searched, and the target value as its parameters.

2. It calculates the index of the middle element.

3. If the middle element matches the target value, it returns the index.

4. If the middle element is greater than the target value, it recursively searches the left sub-array.

5. If the middle element is less than the target value, it recursively searches the right sub-array.

6. If the target value is not present in the array, it returns -1.

7. The main function initializes a sorted array and the element we want to search for. It then calls the binarySearch function and prints the result based on the return value.

8. Binary Search is efficient because with each comparison, it reduces the size of the search space by half.

This provides a detailed understanding of the Binary Search algorithm in Golang.


Comments