Binary Search in GO!

Let's learn how we can implement binary search in golang when we have a sorted array of numbers and an element to be searched for. First let's implement a simple version of finding whether the element is present in the array or not. Later, we will improve it to determine the largest index such that the element in the index is lesser then or equal to the search element.

To implement the simpler version, we will store two end point index of the array starting from 0 and n - 1 where n is the size of the array. With each iteration, we will keep eliminating the half of the array by taking the middle element and comparing it with the search element. Below is the implementation of the same.

func binary_search(array []int64, to_search int64) bool {
  found := false
  low := 0
  high := len(array) - 1
  for low <= high {
    mid := (low + high) / 2
    if array[mid] == to_search {
      found = true
      break
    }
    if array[mid] > to_search {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return found
}

To test the correctness of the above program let's add unit test for the same.

func Test_binary_search(t *testing.T) {
  array := []int64{1, 3, 4, 5}
  to_search1 := 3
  if !binary_search(array, int64(to_search1)) {
    t.Errorf("expected true, got false")
  }

  to_search2 := 6
  if binary_search(array, int64(to_search2)) {
    t.Errorf("expected false, got true")
  }
}

Now let's improve on the above binary search to find the index of the element which is lesser than or equal to the search element. Here, while comparing we will check if the middle element is lesser than or equal to the search element. If it is true, the index can either be the current middle or greater than that. So we assign the index as middle and move on with the right half for further searching. In case the middle element is greater than the search element, we will continue our search on the left half of the array. Here is the implementation and test for the same.

func lower_bound(array []int64, to_search int64) int {
  index := -1
  low := 0
  high := len(array) - 1
  for low <= high {
    mid := (low + high) / 2
    if array[mid] <= to_search {
      low = mid + 1
      index = mid
    } else {
      high = mid - 1
    }
  }
  return index
}

// Test
func Test_lower_bound(t *testing.T) {

  array := []int64{1, 3, 4, 5}
  to_search1 := 0
  to_search2 := 2
  to_search3 := 5
  if lower_bound(array, int64(to_search1)) != -1 {
    t.Errorf("test case failed")
  }
  if lower_bound(array, int64(to_search2)) != 0 {
    t.Errorf("test case failed")
  }
  if lower_bound(array, int64(to_search3)) != 3 {
    t.Errorf("test case failed")
  }
}

We can extend our binary search logic to implement upper_bound, applications with increasing or decreasing functions etc.