Поиск элемента в отсортированном массиве с помощью бинарного алгоритма

Условие

Дан упорядоченный массив целых чисел. Требуется написать функцию бинарного поиска, которая ищет указанное значение и возвращает его позицию в массиве. Если значение отсутствует, функция должна вернуть -1.

sorted := []int{1, 4, 7, 19, 22, 34, 38, 55}
value := 19
// Ожидаемый результат: индекс 3

func binarySearch(sorted []int, value int) int {
    // реализуй
}

Ответ

Бинарный поиск на каждом шаге отбрасывает половину диапазона: время O(log n), дополнительная память O(1). Для 19 результат равен 3.

Используем включительные границы. Пустой срез сразу даёт -1; при дубликатах возвращается любое найденное вхождение, не обязательно первое.

func binarySearch(sorted []int, value int) int {
    lo, hi := 0, len(sorted)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if sorted[mid] == value {
            return mid
        }
        if sorted[mid] < value {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

Предусловие — массив отсортирован по возрастанию.