Golang Program to Implement Binary Search


April 23, 2022, Learn eTutorial
1192

For a better understanding of this example, we always recommend you to learn the basic topics of Golang programming listed below:

Here we are explaining how to write a GO program to search an element from any data structure. There are different types of searching algorithms. In this case, we use a Binary search for finding or searching an element from an array.

Binary search is a fast search algorithm and most important thing is that the Binary search technique only works when elements are in sorted order. It works on the principle of divide and conquers. That means it searches an element in a sorted array by dividing the search space into half and looking for the element in that section. Repeatedly do this process until the value is found or the interval is empty.

In this technique, the first search begins with an interval covering the whole array and it looks for a particular item by comparing the middle item of the collection. If a match occurs then that particular item is returned, otherwise the search continues. Suppose, the value of the search key is greater than the middle element then the search key can only lie in the right half sub-array after the middle element. So we recur for the right half of the middle element. Otherwise, the search key is smaller than the middle element. So we recur for the left half of the middle element. Continue this process until the value is found or the size of the sub-array reduces to zero.

How to implement Binary search

In this GO program, we are importing the “fmt” package to include some standard libraries into the program. After that Main function starts, inside the main, we are doing the whole program. Note that the time complexity of the Binary search algorithm is Ο(log n).

In this GO program, we accept the user's values using the fmt.scanln()  and fmt.println()  methods which are defined under the fmt package. In order to use these functions, we need to import the “fmt” package.

Here variable A holds the array elements. Other variables n, x is used as the size of the array and searching element respectively. Use for loop to read array elements. Note that Binary search only works when elements are in sorted order. So do bubble sort on array elements and display sorted Array using 'for loop' and ‘fmt.Println’.

The variables Low and High are used as the function parameters. Assign Low=0, High=n-1 and perform a binary search by calling the function binarySearch(A, Low, High, num). In this function, compare search element x with the middle element m. Here we calculate the middle element m using the formula if low<=high. If search element x matches with the middle element, we return the middle element index. Otherwise, check x is greater than the middle element, then x can only lie in the right half sub-array after the middle element. So we recur for the right half. Therefore assign low = m + 1 and call the function binarySearch(A, low, high, x). Otherwise, x can only lie in the left half sub-array before the middle element. If so, assign high = m -1 and call the function binarySearch(A, low, high, x) .

Given below are the steps which are used in the Go program to implement binary search. 
 

ALGORITHM:

STEP 1: Import the package fmt

STEP 2: Open the main() to start the program, GO program execution starts with the main()

STEP 3: Declare the variable n, x, temp, Low, High and result

STEP 4: Read the size of the array as n

STEP 5: Define the array A[].

STEP 6: Read the A[] array elements by using a for loop.

STEP 7: Open the nested 'for loop' for implementing the Bubble Sort Algorithm.

STEP 8: Using an if condition check, the comparing element is greater than the compared element

STEP 9: If so, swap the elements using the temporary variable.

STEP 10: Print the sorted Array using 'for loop' and fmt.Println.

STEP 11: Read the number to be searched as x.

STEP 12: Assign the Low as 0 and High as the number of terms n-1.

STEP 13:  Call the function binarySearch (A, Low, Highx) and assign the return value to the result.

STEP 14: Check using an 'if condition' that result is equal to -1. If so, print Element not found

STEP 15: Otherwise print the position of the element found. i.e.; result+1

STEP 16: Exit

Steps To Implement binarySearch (A, Low, Highx) Function

STEP 1: Declare the variable m as the middle element.

STEP 2: Calculate the middle element m using the formula (low + high) / 2, if low=high. Otherwise, return -1 and quit the function.

STEP 3: Check using an 'if' condition that search key x is equal to the Array middle element m. If so, returns the value of m and quit this function.

STEP 4: Using an 'if& 39; condition check, the search key x is less than Array middle element m. If so, high = mid -1 and call the function binarySearch (A, Low, Highx).

STEP 5: Else check the search key x is less than Array middle element if so low = mid + 1 and call the function binarySearch (Alowhighx).

 

Golang Source Code

                                          package main
import  "fmt"
func binarySearch(A[]int, low int, high int, x int) int {
 if low <= high {
  var m int
  m = (high + low) / 2

  if A[m] == x {
   return m
  }

  if A[m] > x {
   return binarySearch(A, low, m-1, x)
  } else {
   return binarySearch(A, m+1, high, x)
  }
 }

 return -1
}

func main() {
 fmt.Println("Enter the size of the array")
 var n int
 fmt.Scan(&n)
 var x int
 A := make([]int, n, 100)
        fmt.Println("Enter elements:")
 for i := 0; i < n; i++ {
  fmt.Scan(&A[i])
 }
 var temp int
        for i := 0; i < n; i++ {
 for j := 0; j <(n-i-1); j++ {
   if A[j] > A[j + 1]{
           temp = A[j];
           A[j] = A[j + 1];
           A[j + 1] = temp;
         }
      }
         }
        fmt.Println("Sorted array:")
 for i := 0; i < n; i++ {
  fmt. Println (A[i])
 }
        fmt.Println("Enter the number to be searched:")
 fmt.Scan(&x)
 var result int
 result = binarySearch(A, 0, n-1, x)
 if result == -1 {
  fmt.Println("Search element not found !")
 } else {
  fmt.Println("Search element found at position: ", result+1)
 }
}

                                      

OUTPUT

Enter the size of the array
5
Enter elements: 
52
32
45
10
90
Sorted array: 
10
32
45
52
90
Enter the number to be searched:
45
Search element found at position:  3