Introduction Binary search is an efficient search algorithm that finds the position of a target value within a sorted array or list. It halves the number of elements to be searched each time, dramatically reducing the number of comparisons needed compared to more naive search algorithms like the linear search. In this blog post, we will delve into the implementation of the binary search algorithm using the Go programming language.
Program Steps
The basic concept of binary search:
Input: A sorted list of elements and a target element to search for.
Processing:
- Determine the middle element of the list.
- If the middle element matches the target, we're done.
- If the middle element is less than the target, search the right half. If the middle element is greater than the target, search the left half.
- Repeat the process until a match is found or the search interval is empty.
Output: Return the index of the target element if found; otherwise, indicate that the element is not in the list.
package main
import "fmt"
// BinarySearch function searches for the target in a sorted array.
func BinarySearch(arr []int, target int) int {
low, high := 0, len(arr)-1
for low <= high {
mid := (low + high) / 2 // Calculate the middle of the array.
if arr[mid] == target {
return mid // Return the index if the target is found.
} else if arr[mid] < target {
low = mid + 1 // Adjust the lower bound.
} else {
high = mid - 1 // Adjust the upper bound.
}
}
return -1 // Return -1 if the target is not found.
}
// Main function to run the program.
func main() {
array := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
target := 70
result := BinarySearch(array, target)
if result != -1 {
fmt.Printf("Element %d is present at index %d.\n", target, result)
} else {
fmt.Printf("Element %d is not present in the array.\n", target)
}
}
Output:
Element 70 is present at index 6.
Comments
Post a Comment
Leave Comment