Program Structure
This program implements the binary search algorithm in Go. The binary search algorithm is an efficient method for finding a target value within a sorted array. The search repeatedly divides the portion of the array that could contain the target value in half until you’ve narrowed down the possible locations to just one.
Code Implementation
package main
import (
"fmt"
)
// BinarySearch performs a binary search on a sorted array.
// It returns the index of the target if found, or -1 if not found.
func BinarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2 // Prevents potential overflow
// Check if the target is at mid
if arr[mid] == target {
return mid
}
// If the target is greater, ignore the left half
if arr[mid] < target {
left = mid + 1
} else { // If the target is smaller, ignore the right half
right = mid - 1
}
}
// Target was not found
return -1
}
func main() {
// Sample sorted array
arr := []int{2, 3, 4, 10, 40}
target := 10
// Perform binary search
result := BinarySearch(arr, target)
// Output the result
if result != -1 {
fmt.Printf("Element found at index: %d\n", result)
} else {
fmt.Println("Element not found in the array.")
}
}
Explanation of the Code
1. Package Declaration
The program starts with the declaration of the main package.
2. Importing Packages
The fmt package is imported to enable formatted I/O operations.
3. Binary Search Function
The BinarySearch function takes a sorted array and a target value as input parameters:
left: Index of the first element in the current search range.right: Index of the last element in the current search range.mid: Index of the middle element calculated in each iteration.
The function continues to narrow down the search range until it either finds the target or exhausts the search space.
4. Main Function
The main function initializes a sample sorted array and a target value. It then calls the BinarySearch function and outputs the result to the console.
Conclusion
The binary search algorithm is an efficient way to locate elements in a sorted array, offering a time complexity of O(log n). The provided Go implementation demonstrates how to perform binary search with clear and concise logic.
