Напишите бинарный поиск: по отсортированному по неубыванию слайсу и значению
target вернуть индекс элемента, равного target, или -1, если такого нет.
Функция должна работать для любого упорядочиваемого типа. Пакеты sort и
slices не использовать.
// BinarySearch возвращает индекс какого-либо элемента nums, равного target, или -1.
func BinarySearch[T cmp.Ordered](nums []T, target T) int
Примеры
nums = [-1, 0, 3, 5, 9, 12], target = 9 → 4
nums = [-1, 0, 3, 5, 9, 12], target = 2 → -1
nums = [], target = 1 → -1
nums = [2, 2, 2], target = 2 → 0, 1 или 2 (любой подходит)
nums = ["go", "java", "rust"], target = "rust" → 2
Ограничения
0 ≤ len(nums) ≤ 10⁶, слайс отсортирован по неубыванию, повторы возможны.- Если
target встречается несколько раз, верните индекс любого вхождения.
- O(log n) на запрос: функцию вызывают много раз на большом слайсе.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.