Searching efficiently is one of the most essential skills in programming. Whenever you have a large dataset and need to locate a specific item, doing it manually or using a simple linear search can be slow. This is where Binary Search comes in. It is a fast and effective method for searching in sorted arrays, using a divide-and-conquer approach.
with hands-on learning.
get the skills and confidence to land your next move.
Binary Search works by repeatedly dividing the search interval in half. It starts with the middle element of the array. If the middle element is the target, the search is complete. If the target is smaller, the search continues in the left half; if it is larger, the search continues in the right half. This method drastically reduces the number of comparisons compared to Linear Search, making it a crucial algorithm for beginners and professionals alike.
Program 1: Iterative Binary Search
The first program demonstrates the classic iterative approach to Binary Search. It searches a sorted array and returns the index of the target element.
package main
import "fmt"
func binarySearch(arr []int, target int) int {
low := 0
high := len(arr) - 1
for low <= high {
mid := low + (high-low)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
func main() {
numbers := []int{10, 20, 30, 40, 50, 60}
target := 40
index := binarySearch(numbers, target)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}This program works by maintaining low and high pointers to define the search range. The middle element is calculated each time, and the range is adjusted depending on whether the target is smaller or larger. Iterative Binary Search is efficient and avoids the overhead of recursive calls, which is ideal for beginners to see how loops can simplify the search process.
Program 2: Recursive Binary Search
Recursion is a natural fit for Binary Search. This program implements the search using a recursive approach.
package main
import "fmt"
func binarySearchRec(arr []int, target int, low, high int) int {
if low > high {
return -1
}
mid := low + (high-low)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
return binarySearchRec(arr, target, mid+1, high)
} else {
return binarySearchRec(arr, target, low, mid-1)
}
}
func main() {
numbers := []int{5, 15, 25, 35, 45, 55}
target := 25
index := binarySearchRec(numbers, target, 0, len(numbers)-1)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}The recursive version reduces the problem size in each function call by half. If the target is smaller than the middle element, the function searches the left half; otherwise, it searches the right half. This method demonstrates recursion in a very clear and practical way, helping beginners understand how problems can be broken down into smaller subproblems.
Program 3: Binary Search for Strings
Binary Search is not limited to numbers; it can also work with strings in a sorted slice. This program shows how to search for a specific word alphabetically.
package main
import "fmt"
func binarySearchString(arr []string, target string) int {
low := 0
high := len(arr) - 1
for low <= high {
mid := low + (high-low)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
func main() {
names := []string{"Draco", "Harry", "Hermione", "Luna", "Ron"}
target := "Hermione"
index := binarySearchString(names, target)
if index != -1 {
fmt.Printf("Name %s found at index %d\n", target, index)
} else {
fmt.Printf("Name %s not found in the array\n", target)
}
}This program compares strings using the standard lexicographical order. By using Binary Search on a sorted string slice, it efficiently finds the target word. Beginners can see that the same algorithm works for any comparable data type.
Program 4: Binary Search for Multiple Occurrences
Sometimes the target may appear multiple times. This version finds all indices of the target value in a sorted array.
package main
import "fmt"
func binarySearchAll(arr []int, target int) []int {
indices := []int{}
index := binarySearch(arr, target)
if index == -1 {
return indices
}
// Check left side
left := index - 1
for left >= 0 && arr[left] == target {
indices = append([]int{left}, indices...)
left--
}
// Add middle index
indices = append(indices, index)
// Check right side
right := index + 1
for right < len(arr) && arr[right] == target {
indices = append(indices, right)
right++
}
return indices
}
func binarySearch(arr []int, target int) int {
low := 0
high := len(arr) - 1
for low <= high {
mid := low + (high-low)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
func main() {
numbers := []int{5, 10, 10, 10, 20, 25, 30}
target := 10
indices := binarySearchAll(numbers, target)
if len(indices) > 0 {
fmt.Printf("Element %d found at indices %v\n", target, indices)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}This approach first finds one occurrence of the target, then checks both left and right neighbors to collect all indices. It’s useful for datasets where duplicates exist and gives beginners insight into how to extend a basic algorithm.
Frequently Asked Questions (FAQ)
Binary Search is fast, but beginners often have questions.
Q1: What is Binary Search?
Binary Search is an efficient algorithm to find an element in a sorted array by repeatedly dividing the search range in half.
Q2: What is the time complexity of Binary Search?
The time complexity is O(log n), which makes it much faster than Linear Search for large datasets.
Q3: Can Binary Search work with unsorted arrays?
No. The array must be sorted first; otherwise, the search logic will fail.
Q4: Is Binary Search recursive or iterative?
It can be implemented both ways. Iterative is simple and memory-efficient, while recursive is elegant and demonstrates divide-and-conquer principles.
Q5: Can Binary Search work with strings?
Yes. As long as the array is sorted lexicographically, Binary Search works for strings and other comparable types.
Conclusion
Binary Search is a cornerstone algorithm for efficient searching in programming. By using divide-and-conquer, it drastically reduces the number of comparisons needed to find an element, making it far more efficient than Linear Search.
Beginners can start with the iterative version to understand loops and ranges, then explore recursion to see how divide-and-conquer works naturally. You can also experiment with strings and multiple occurrences to deepen your understanding. Practice is key — the more you use Binary Search in different scenarios, the more intuitive and powerful it becomes in your GoLang toolkit.
