Go Program to Implement Binary Search

Introduction

Binary Search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half, or if it’s greater, it continues in the upper half. This process continues until the value is found or the interval is empty.

Problem Statement

Create a Go program that:

Prompts the user to enter the number of elements in a sorted array.
Takes input for the elements of the array.
Prompts the user to enter the target element to search for.
Implements Binary Search to find the target element.
Displays whether the element is found and its position in the array (if found).

Example:

Input: Array elements: [1, 2, 3, 4, 5, 6, 7, 8, 9], Target element: 5
Output: Element 5 found at index 4

Solution Steps

Import the fmt Package: Use import "fmt" to include the fmt package for formatted I/O operations.
Write the Main Function: Define the main function, which is the entry point of every Go program.
Input the Number of Elements: Use fmt.Scanln to take input from the user for the number of elements in the array.
Input the Array Elements: Use a loop to input the elements of the array from the user.
Input the Target Element: Prompt the user to enter the target element to search for.
Implement Binary Search: Write a function to perform Binary Search and return the index of the target element if found.
Display the Result: Use fmt.Println to display whether the element was found and its index.

Go Program

package main

import "fmt"

/**
 * Go Program to Implement Binary Search
 * Author: https://www.javaguides.net/
 */
func main() {
    // Step 1: Declare a variable to hold the number of elements in the array
    var n int

    // Step 2: Prompt the user to enter the number of elements
    fmt.Print("Enter the number of elements in the sorted array: ")
    fmt.Scanln(&n)

    // Step 3: Declare an array to hold the elements
    array := make([]int, n)

    // Step 4: Input the elements of the array
    fmt.Println("Enter the elements of the array in sorted order:")
    for i := 0; i < n; i++ {
        fmt.Scanln(&array[i])
    }

    // Step 5: Prompt the user to enter the target element to search for
    var target int
    fmt.Print("Enter the target element to search for: ")
    fmt.Scanln(&target)

    // Step 6: Perform Binary Search
    index := binarySearch(array, target)

    // Step 7: Display the result
    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)
    }
}

// Function to perform Binary Search
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 // Target element found
        }

        if arr[mid] < target {
            low = mid + 1 // Search the right half
        } else {
            high = mid - 1 // Search the left half
        }
    }

    return -1 // Target element not found
}

Explanation

Step 1: Declare Variables

The variable n is declared to store the number of elements in the array.

Step 2: Input the Number of Elements

The program prompts the user to enter the number of elements using fmt.Print. The fmt.Scanln function reads the input and stores it in the n variable.

Step 3: Declare the Array

An array array is created using make to hold n integer elements.

Step 4: Input the Array Elements

The program uses a for loop to prompt the user to enter each element of the array, storing the input in the corresponding index of array.

Step 5: Input the Target Element

The program prompts the user to enter the target element to search for using fmt.Print. The fmt.Scanln function reads the input and stores it in the target variable.

Step 6: Implement Binary Search

The binarySearch function takes the sorted array and the target element as arguments. It initializes low and high pointers and uses a loop to perform the binary search. If the middle element is the target, it returns the index. If the target is greater than the middle element, it searches the right half, otherwise, it searches the left half.

Step 7: Display the Result

The program checks the result of binarySearch. If the index is not -1, it prints the index where the element was found; otherwise, it indicates that the element was not found.

Output Example

Example 1:

Enter the number of elements in the sorted array: 9
Enter the elements of the array in sorted order:
1
2
3
4
5
6
7
8
9
Enter the target element to search for: 5
Element 5 found at index 4

Example 2:

Enter the number of elements in the sorted array: 5
Enter the elements of the array in sorted order:
10
20
30
40
50
Enter the target element to search for: 25
Element 25 not found in the array

Conclusion

This Go program demonstrates how to implement the Binary Search algorithm to efficiently find an element in a sorted array. It covers basic programming concepts such as arrays, loops, and conditional statements. This example is useful for beginners learning Go programming and understanding how to implement and optimize search algorithms.