Golang Binary Search Algorithm

Ghaly Fadhillah

410

Feb, 22 2023 14:45:17

What is Binary Search?

Binary search is an algorithm used to search for a specific value within a sorted list or array. The basic idea behind binary search is to repeatedly divide the list in half, until the target value is found or determined to be absent.

Here's how binary search works:

1.   Given a sorted list of n elements and a target value, we start by comparing the target value with the middle element of the list.

2.   If the target value is equal to the middle element, we have found the target and the search is complete.

3.   If the target value is less than the middle element, we can eliminate the second half of the list, since the target cannot be in that portion of the list.

4.   If the target value is greater than the middle element, we can eliminate the first half of the list, since the target cannot be in that portion of the list.

5.   We then repeat steps 1 through 4 on the remaining half of the list, until the target is found or determined to be absent.

Binary search has a time complexity of O(log n), which makes it much faster than a linear search, especially for larger lists. However, the list must be sorted before the binary search can be performed. 

 

What is the use of Binary Search?

It is commonly used in computer science and programming for tasks such as:

1.   Searching a database for a specific record or value.

2.   Finding a specific value within a large collection of data.

3.   Implementing search algorithms in programming languages.

4.   Searching through a sorted list of words or terms.

5.   Optimizing certain algorithms that require searching through large collections of data.

 

The Example of Golang Binary Search Algorithm 

 

package main
import "fmt"
func binarySearch(arr []int, target int) int {
start := 0
end := len(arr) - 1
for start <= end {
mid := (start + end) / 2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
start = mid + 1
} else {
end = mid - 1
}
}
return -1
}
func main() {
arr := []int{1, 3, 4, 6, 8, 9, 11}
target := 4
result := binarySearch(arr, target)
if result == -1 {
fmt.Println("Element not found in the array.")
} else {
fmt.Printf("Element found at index %d.\n", result)
}
}