В этой статье блога мы рассмотрим различные методы поиска ближайшего числа к заданной цели в массиве с использованием языка программирования Go. Мы предоставим примеры кода для каждого метода, чтобы продемонстрировать их реализацию. Независимо от того, являетесь ли вы новичком или опытным разработчиком Go, это руководство поможет вам понять различные подходы к решению этой распространенной проблемы.

Методы:

1. Линейный поиск.
   Метод линейного поиска включает в себя перебор массива и сравнение каждого элемента с целевым числом. Мы отслеживаем ближайшее найденное число и обновляем его всякий раз, когда встречается более близкое число.

func findNearestLinear(arr []int, target int) int {
    nearest := arr[0]
    diff := abs(target - nearest)
    for _, num := range arr {
        if abs(target-num) < diff {
            diff = abs(target - num)
            nearest = num
        }
    }
    return nearest
}

1. Сортировка и двоичный поиск.
   Этот метод включает в себя сначала сортировку массива, а затем выполнение двоичного поиска для поиска ближайшего числа. Используя двоичный поиск, мы можем эффективно найти ближайшее к цели число.

import (
    "sort"
)
func findNearestBinary(arr []int, target int) int {
    sort.Ints(arr)
    index := sort.SearchInts(arr, target)

    if index < len(arr) && arr[index] == target {
        return target
    }
    if index == 0 {
        return arr[0]
    }
    if index == len(arr) {
        return arr[len(arr)-1]
    }
    if abs(target-arr[index-1]) < abs(target-arr[index]) {
        return arr[index-1]
    }
    return arr[index]
}

1. Двоичное дерево поиска.
   Использование двоичного дерева поиска (BST) также может оказаться эффективным способом поиска ближайшего числа. Мы создаем BST из массива и проходим по нему, чтобы найти ближайшее к цели число.

type Node struct {
    Value       int
    Left, Right *Node
}
func constructBST(arr []int) *Node {
    if len(arr) == 0 {
        return nil
    }
    mid := len(arr) / 2
    root := &Node{Value: arr[mid]}
    root.Left = constructBST(arr[:mid])
    root.Right = constructBST(arr[mid+1:])
    return root
}
func findNearestBST(root *Node, target int) int {
    closest := root.Value
    for root != nil {
        if abs(target-root.Value) < abs(target-closest) {
            closest = root.Value
        }
        if target < root.Value {
            root = root.Left
        } else if target > root.Value {
            root = root.Right
        } else {
            break
        }
    }
    return closest
}