JavaScript 알고리즘(10) Linear Search

 

Linear Search 는 값을 찾을 때 순서대로 하나하나씩 다 검사하는 searching algorithm 이다.

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, 

 

우리가 흔히 알고 있는 for문을 사용하여 하나하나씩 검사하는 방법을 사용한다.

이게 가장 기본적인 방식이고 이 알고리즘을 기준으로 여러 알고리즘들을 비교할 수 있을 것 같다.

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

linearSearch([34, 56, 1, 2], 1) // 2

 

 

Big o notation 에서는 아래와 같이 표기할 수 있다.

Best - O(1)       // 한방에 찾는 경우 
Average - O(n) // 검사
Worst - O(n)     // 검사