Go Program for Binary Search with Example and Explanation

A Go program for binary search uses a loop to repeatedly divide the sorted array and check the middle element with for low <= high and adjusts low or high until the target is found or not. Example: func binarySearch(arr []int, target int) int { low, high := 0, len(arr)-1; for low <= high { mid := (low + high) / 2; if arr[mid] == target { return mid } else if arr[mid] < target { low = mid + 1 } else { high = mid - 1 } } return -1 }.

Examples

Inputarr = [1, 3, 5, 7, 9], target = 5

Output2

Inputarr = [2, 4, 6, 8, 10], target = 7

Output-1

Inputarr = [10, 20, 30, 40, 50], target = 10

Output0

How to Think About It

To do binary search, first imagine the list is sorted. You look at the middle item and compare it to the target. If it matches, you are done. If the target is smaller, you only look at the left half next. If it is bigger, you look at the right half. You keep doing this until you find the target or the search space is empty.

Algorithm

1

Start with two pointers: low at start, high at end of array.

2

While low is less than or equal to high:

3

Calculate middle index as (low + high) / 2.

4

If middle element equals target, return middle index.

5

If middle element is less than target, move low to mid + 1.

6

Else, move high to mid - 1.

7

If not found, return -1.

Code

go

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

func main() {
    arr := []int{1, 3, 5, 7, 9}
    target := 5
    result := binarySearch(arr, target)
    fmt.Println(result)
}

Output

2

Dry Run

Let's trace searching for 5 in [1, 3, 5, 7, 9] through the code

1

Initialize pointers

low = 0, high = 4 (array length - 1)

2

Calculate mid and compare

mid = (0 + 4) / 2 = 2, arr[mid] = 5

3

Check if arr[mid] equals target

arr[2] == 5, which matches target 5, return 2

low	high	mid	arr[mid]	comparison
0	4	2	5	arr[mid] == target, return 2

Why This Works

Step 1: Divide and conquer

The code splits the array into halves by calculating the middle index with mid = (low + high) / 2.

Step 2: Compare middle element

It compares the middle element with the target using if arr[mid] == target to find a match quickly.

Step 3: Adjust search range

If the middle element is less than the target, it moves the low pointer up; otherwise, it moves the high pointer down to narrow the search.

Alternative Approaches

Recursive binary search

go

package main

import "fmt"

func binarySearchRecursive(arr []int, target, low, high int) int {
    if low > high {
        return -1
    }
    mid := (low + high) / 2
    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        return binarySearchRecursive(arr, target, mid+1, high)
    } else {
        return binarySearchRecursive(arr, target, low, mid-1)
    }
}

func main() {
    arr := []int{1, 3, 5, 7, 9}
    target := 7
    result := binarySearchRecursive(arr, target, 0, len(arr)-1)
    fmt.Println(result)
}

Uses recursion instead of a loop; easier to read but uses more memory due to call stack.

Using sort.Search from standard library

go

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{1, 3, 5, 7, 9}
    target := 7
    index := sort.Search(len(arr), func(i int) bool { return arr[i] >= target })
    if index < len(arr) && arr[index] == target {
        fmt.Println(index)
    } else {
        fmt.Println(-1)
    }
}

Uses Go's built-in binary search function for cleaner code but less control.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search halves the search space each step, so it runs in logarithmic time, O(log n), where n is the number of elements.

Space Complexity

The iterative version uses constant extra space O(1) because it only stores a few variables.

Which Approach is Fastest?

Iterative binary search is fastest and uses less memory than recursive. Using Go's sort.Search is convenient but adds a small overhead.

Approach	Time	Space	Best For
Iterative binary search	O(log n)	O(1)	Fastest and memory efficient
Recursive binary search	O(log n)	O(log n)	Clear code but uses more memory
Go sort.Search	O(log n)	O(1)	Quick use of built-in function