알고리즘 검색

                   -Intro to Searching
                   -Intro to Linear Search 
                   -Intro to Binary Search

검색 소개

검색은 응용 프로그램에 일반적으로 사용되는 기능입니다. Google과 같은 검색 엔진은 복잡한 알고리즘을 기반으로 결과를 최적화합니다. Youtube에는 동영상을 찾고 추천하는 검색 알고리즘이 있습니다. 검색은 응용 프로그램이 유용하기 위한 기본 절차입니다. 검색 알고리즘을 구현하는 방법에는 여러 가지가 있습니다. 특정 상황에서는 다른 것보다 특정 검색을 사용하는 것이 더 합리적일 수 있습니다.

선형 검색 소개

JavaScript에는 검색 알고리즘을 위한 많은 배열 메서드가 포함되어 있습니다. 일부는 indexOf, 포함, 찾기, findIndex입니다.

선형 탐색은 한 번에 한 간격을 이동하여 작동합니다. 또한 한 번에 하나의 요소를 제거합니다.

선형 검색 예

function linearSearch(arr, val){
    for(var i = 0; i < arr.length; i++){
        if(arr[i] === val) return i;
    }
    return -1;
}

linearSearch([34,51,1,2,3,45,56,687], 100)

이진 검색 소개

이진 검색은 한 번에 하나의 요소를 제거하는 대신 한 번에 나머지 요소의 절반을 제거하기 때문에 선형 검색보다 효율적입니다.

이진 검색 예

function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

// Refactored Version
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)