Introduction

Binary search is a highly efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half, or if the value is greater, it continues in the upper half. This process repeats until the value is found or the interval is empty.

The objective of this tutorial is to demonstrate how to implement the binary search algorithm in Go programming language. Binary search has a time complexity of O(log n), making it significantly faster than linear search algorithms, which have a time complexity of O(n).

Binary Search Code in Go

// Binary Search Algorithm in Go

package main

import "fmt"

// BinarySearch function to perform binary search on a sorted array
func BinarySearch(arr []int, target int) int {
    low := 0
    high := len(arr) - 1

    // Iterating while the low index is less than or equal to the high index
    for low <= high { mid := (low + high) / 2 // If the target is found, return the index if arr[mid] == target { return mid } // If target is smaller, discard the right half if arr[mid] > target {
            high = mid - 1
        } else {
            // If target is larger, discard the left half
            low = mid + 1
        }
    }

    // If the target is not found, return -1
    return -1
}

func main() {
    // Sorted array for testing binary search
    arr := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}
    target := 15

    // Call BinarySearch function
    result := BinarySearch(arr, target)

    // Output result
    if result != -1 {
        fmt.Printf("Element %d found at index %d.\n", target, result)
    } else {
        fmt.Println("Element not found.")
    }
}
        

Explanation of the Program Structure

The Go program begins by defining a BinarySearch function that accepts two parameters:

• arr: A sorted slice of integers where the search will be conducted.
• target: The integer value to be found within the array.

The function works by using a while loop to repeatedly divide the search range in half. At each iteration, the midpoint of the current range is calculated and compared with the target value. If a match is found, the index is returned. If the target is smaller or larger than the middle value, the search continues in the corresponding half.

The main function demonstrates how to use the BinarySearch function. It defines a sorted array and sets a target value. The result is printed to the console: if the element is found, its index is displayed; otherwise, a “not found” message is shown.

How to Run the Program

1. Ensure you have Go installed on your system. You can download it from here.
2. Copy and paste the code into a file named binary_search.go.
3. Open a terminal and navigate to the directory containing the file.
4. Run the following command to execute the program:

   go run binary_search.go

5. The output will display the result, either the index of the target element or a message indicating that the element was not found.