JavaScript -선형 검색/완전 탐색(Linear Search)

안녕하세요.

Hynn 입니다.

 

이번 포스팅에서는 이제 Array(배열)이 무작위로 나열되어 있을때, 이를 일일히 확인하지 않더라도, 특정 값(Value) 를 검색하는 기능을 구현하는 방법을 작성해보겠습니다.

이 검색의 명칭은 선형검색 혹은 완전 탐색이라고 하며, 정식 명칭은 Linear Search 입니다.

 

========

1. Linear Search 

2. 예제 작성하기

========

 

1. Linear Search 

 

Linear Search 는 선형 검색/완전 탐색이라고도 불리우는 알고리즘이라고도 합니다.

이 방식은 단방향 (JavaScript 에서는 왼쪽에서 오른쪽) 으로 탐색을 진행하여 원하는 데이터를 검색하는 방식으로 보자면 매우 단순한 방형태의 알고리즘입니다. 

이는 구현에서의 편리성을 장점으로 가져오지만, 단점으로는 모든 데이터를 일일히 확인하기때문에, 배열의 위치 상 뒤에 있을 수록 시간 복잡도, 즉 효율이 점점 떨어지는 검색방법 입니다. 이는 이후에 다른 알고리즘을 사용하여 검색하는 방법도 존재하지만, 오늘은 이 기본적인 Linear Search만 다루도록 하겠습니다.

 

2. 예제 작성하기

먼저, 기본적인 JavaScript 작성은 아래와 같습니다.

arr = [10,3,2,124,14,213,41,151,23,123,41,2415,123,124]

function linearSearch (array, target){
    const length = array.length

    for(let i = 0; i<length; i++){
        if(array[i] === target){
            return i
        }
    }

    return "There are no values in the list"
}

 

먼저 Array 형태의 배열을 하나 무작위로 작성했습니다.

여기서 우리는 특정한 숫자를 검색하고자 하는 방식을 취할겁니다.

 

그를 위해 함수를 선언하고, LinearSearch 를 입력후, ()에는 아래의 순서에 따라 입력이 필요합니다. 괄호 첫번째에 들어가야 할 매개변수는 배열을 넣어야 합니다. 즉 위 함수에서는 찾고자 하는 것이 arr 라는 변수명이 될 것입니다. 두번째 매개변수는 Target, 즉 찾고자 하는 숫자가 입력되어야 합니다. 숫자가 아니라 "값" 이라고 표현하는 것이 더 정확할 거 같네요.

 

그리고 함수에는 이제 반복문을 이용해서 조건을 부여해야 합니다.

위의 설명에서 말씀드렷듯 선형검색은 단방향으로 모든 데이터를 하나하나 체크하여 일치값이 있는지를 검색하는 알고리즘이라는 설명을 드렸습니다.

즉 반복문을 사용하여 검색을 이용해야 하고, 우리는 이미 index 값이 0부터 시작한다는 것을 잘 알고 있습니다.

 

즉 For (반복문) 에는 i = 0; , i < length; i++ 로 작성해야 하는 것이죠. 당연히 Index는 0으로 시작하므로 i 는 0으로 시작해야 하고,i는 Length 의 값보다 작아야 하며, i가 한번 반복될때마다 +1 씩 진행되어야 하니까요. 

그러면 반복문의 조건이 완성되었습니다.

 

이제 조건문을 부여하여 일치하는지를 확인해야 합니다. 즉 IF 문에서는 array 에서 대괄호표기법을 사용해 [i] 배열에 위치한 값이 Target 과 일치하는지를 연산자를 통해 입력해주어야 합니다. 당연히 이 조건에 일치하지 않는다면 return 에서 "There are no values in the list" 을 출력하도록 설정하는 것입니다.

 

이제 작성이 완료되었으니, 실제 검색을 위해 변수를 세개 정도 생성해서 작성해보도록 하겠습니다.

 

arr = [10,3,2,124,14,213,41,151,23,123,41,2415,123,124]

function linearSearch (array, target){
    const length = array.length

    for(let i = 0; i<length; i++){
        if(array[i] === target){
            return i
        }
    }

    return "value is not in the list"
}

const search1 = linearSearch(arr,14123)
const search2 = linearSearch(arr,123)
const search3 = linearSearch(arr,41)

console.log(search1)
console.log(search2)
console.log(search3)

 

 

단순 검색에서는 아주 간편하고, 빠르게 접근할 수 있는 장점을 가지고 있는 LinearSearch 입니다.

하지만 위에서 언급한데로 데이터의 양이 방대해질수록 이는 시간복잡도에서 효율이 떨어지는 친구라 할 수 있습니다.

 

추후 포스팅에서 다른 검색방법도 다루도록 할 예정이지만,

가장 기초적인 방법에 대해서는 이해하는 포스팅이 되시길 바랍니다.

 

감사합니다.