Бинарный поиск в GO! |

Давайте узнаем, как мы можем реализовать бинарный поиск в golang, когда у нас есть отсортированный массив чисел и элемент для поиска. Сначала давайте реализуем простую версию определения того, присутствует ли элемент в массиве или нет. Позже мы улучшим его, чтобы определить наибольший индекс, чтобы элемент в индексе был меньше или равен элементу поиска.

Чтобы реализовать более простую версию, мы будем хранить два индекса конечных точек массива, начиная с 0 и n — 1, где n — размер массива. С каждой итерацией мы будем удалять половину массива, беря средний элемент и сравнивая его с элементом поиска. Ниже приведена реализация того же самого.

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
}

Чтобы проверить правильность вышеуказанной программы, давайте добавим для нее модульный тест.

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")
  }
}

Теперь давайте улучшим приведенный выше бинарный поиск, чтобы найти индекс элемента, который меньше или равен искомому элементу. Здесь при сравнении мы будем проверять, меньше или равен средний элемент элементу поиска. Если это правда, индекс может быть либо текущим средним значением, либо большим. Поэтому мы назначаем индекс как средний и переходим к правой половине для дальнейшего поиска. В случае, если средний элемент больше элемента поиска, мы продолжим поиск в левой половине массива. Вот реализация и тест для того же.

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")
  }
}

Мы можем расширить нашу логику бинарного поиска для реализации upper_bound, приложений с возрастающими или убывающими функциями и т. д.