다차원 데이터에 대한 동기를 부여해주는 사용 사례인 **최근접 이웃 탐색(nearest-neighbor search)**을 소개한다.

1. 최근접 이웃 탐색 소개

: 주어진 탐색 목표와 가장 가까운 데이터 점을 찾는다.

1.1 선형 스캔을 이용한 최근접 이웃 탐색

실수 범위인 수직 선상에서 최근접 이웃 탐색이라는 맥락에서 두 가지 이점이 있다.

선형 스캔 최근접 이웃 알고리즘 코드

# LinearScanClosestNeighbor 함수는 주어진 배열 A에서 target 값과의 거리가 가장 가까운 요소를 찾습니다.

LinearScanClosestNeighbor(Array: A, Float: target, Function: dist):
    # 배열의 길이를 계산
    Integer: N = length(A)
    
    # 배열이 비어있는 경우 null 반환
    IF N == 0:
        return null

    # 초기 후보 값으로 배열의 첫 번째 요소를 설정
    Float: candidate = A[0]
    # 첫 번째 요소와 target 간의 거리를 계산
    Float: closest_distance = dist(target, candidate)
    Integer: i = 1

    # 배열을 순차적으로 탐색하면서 가장 가까운 값을 찾음
    WHILE i < N:
        # 현재 요소와 target 간의 거리 계산
        Float: current_distance = dist(target, A[i])
        
        # 현재 거리가 기존의 최소 거리보다 작다면 업데이트
        IF current_distance < closest_distance:
            closest_distance = current_distance
            candidate = A[i]
        
        # 다음 요소로 이동
        i = i + 1

    # 가장 가까운 요소 반환
    return candidate


// LinearScanClosestNeighbor implementation in JavaScript
function LinearScanClosestNeighbor(array, target, dist) {
    const N = array.length;
    if (N === 0) return null;

    let candidate = array[0];
    let closestDistance = dist(target, candidate);

    for (let i = 1; i < N; i++) {
        const currentDistance = dist(target, array[i]);
        if (currentDistance < closestDistance) {
            closestDistance = currentDistance;
            candidate = array[i];
        }
    }

    return candidate;
}

// Example usage
const array = [1, 3, 7, 8, 10];
const target = 6;

// Distance function: absolute difference
const distance = (a, b) => Math.abs(a - b);

const closestNeighbor = LinearScanClosestNeighbor(array, target, distance);

console.log(`The closest neighbor to ${target} is ${closestNeighbor}`);