[탐색] 선형 탐색 (linear search)

선형 탐색

배열 내에서 특정한 값을 찾기 위해 사용할 수 있는 가장 심플한 방법은

배열 내의 모든 엘리먼트를 A부터 Z까지 쭉 훑어서 찾는 것이다.

이 방법이 선형 탐색이다.

 

---

우리는 선형 탐색을 이미 사용중이다.

 

우리는 이미 자바스크립트에서 선형 탐색을 사용하고 있었을 것이다.

자바스크립트에는 몇 종류의 선형 탐색 메서드가 내장되어 있다.

• Array.indexOf
• Array.includes
• Array.find
• Array.findIndex

네개의 메서드는 리턴하는 값은 다르지만

동작하는 로직은 크게 다를바가 없다.

배열 내 모든 엘리먼트를 순환하는 로직이라는 것이다. (선형 탐색)

 

 

단어를 너무 어렵게만 생각하지 말자

배열을 A부터 Z까지 모두 순회하며 값을 찾아낸다면

그것은 선형 탐색이다.

 

아래의 코드처럼 말이다.

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

 

선형탐색은 input의 길이에 따라 연산숫자가 비례하여 올라가게 되므로

O(N)의 시간복잡도를 가지게 된다.