Binary Search Algorithm with Go Example Code

Binary search is an algorithm for finding an element from the sorted list/array continuously chopping the search area in half.

In binary search searching is not starts from the beginning as in Linear Search, searching starts from the middle of the list.

Let’s take as an example this list of numbers. In this case, searching starts from the 5.

Note: in the binary search list/arr must be sorted

Let’s look deeper through this example. We have array which includes numbers from 0 to 9 and we are searching for index of the 3. We will define 3 variables left, right and mid(middle). Left and right shows the indexes of the array. Mid always points the middle of the array.

1. Initially, left = 0, right = len(list)-1 (full list)
2. Calculate the value of the mid = (low + high) / 2
3. Then comparation of the list[mid] and target(which is 3 in this example). If they are equal you target was found you will end the program here.
4. If target is greater than the number in the middle, we move the left to one next element from the middle: low = mid + 1. Otherwise, move the right pointer one previous element from the middle.
5. And you repeat until you find the target.

Here is the binary search in Go

package main

import "fmt"

func findMe(nums []int, target int) int {
 left := 0
 right := len(nums) - 1

 for left <= right {
  // Calculate middle index
  mid := (left + right) / 2
  if nums[mid] == target {
   return mid
  }
  if nums[mid] < target {
   // If target is greater, focus on the right half
   left = mid + 1
  } else {
   // If target is less, focus on the left half
   right = mid - 1
  }
 }
 // if tartget not fount return -1
 return -1
}

func main() {
 fmt.Println(findMe([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 8)) //resp 7
 fmt.Println(findMe([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 4)) //resp 3
}

You can visually represent the binary search algorithm to make it easier to understand:

https://www.crio.do/blog/content/images/2022/08/Sequential-Search.gif