7.26 Dev.Feedback ( 검색 알고리즘 선형검색, 이진검색)

저번주부터 귀에 염증이 심하게 생겨서 제대로 된 공부를 하지 못했다. 포스팅도 당연히...

조금씩 컨디션을 챙겼고, 조금이라도 괜찮을 때마다 정리하려고 한다.

 

검색 알고리즘

먼저 우리가 어떤 데이터를 다룰 때, 검색은 당연히 필요한 경우이다. 이 데이터들은 무분별하게 나열이 된 경우가 있을 것이고, 혹은 차곡차곡 순서에 맞게 정렬(sorted)된 경우가 있을 것이다. 어떠한 경우든 나열된 데이터 중에서 우리가 원하는 데이터를 찾아내는 것은 매우 중요하다. 

 

선형검색(Linear Search)

나열된 어떤 데이터 구조의 처음부터 검색을 하는 방법이다. 예시를 들어 설명해보면

let arr = [2, 4, 7, 20, 12, 6, 21, 692, 3];

function findNumb(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 6) console.log("Gotcha!!");
    console.log(i);
  }
}

위의 이미지처럼  원하는 숫자를 찾기위해 배열의 모든 인덱스를 하나 하나 둘러보는 것을 말할 수 있다.

이런 경우 수행시간이 선형적으로 증가하게 되는데, 이 경우 만일 원하는 숫자가 맨 앞에 있는 경우라면 빠르게 해결이 가능하겠지만, 혹시나 가장 마지막 부분에 있거나 아니면 아예 존재하지 않거나하는 경우 거기에 나열된 데이터의 길이가 수천 수백만 혹은 그 이상까지 늘어나게 되면, 어떤 기능이 작동하는데 있어 엄청난 시간이 들게 된다.

그래서 등장한 것이 이진검색이다.

 

이진검색(Binary Search)

이진검색은 자료 가운데 있는 항목을 키 값과 비교하여 그 항목이 키 값보다 크다면 오른쪽을 검색하고, 키 값보다 작다면 왼쪽을 검색하는 방법이다. 

 

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

위의 이미지가 이진검색과 선형검색(Linear 과 Sequential은 비슷한 의미)의 차이를 보여주는 하나의 예시이다.

위의 이미지의 이진검색을 보면 가장 중앙의 항목을 탐색 해보고, 그 숫자가 큰 경우 왼쪽의 모든 부분들을 아예 염두에 두지 않고 지워버리는 것을 볼 수 있다. 그 나머지 반을 삭제하고 탐색을 진행하기에 어떤 경우에는 선형검색보다 더 효율적으로 원하는 자료를 찾아낼 수 있다.

하지만, 이진검색을 할 때 중요한 점이 있다. 이진검색을 하고자 하는 데이터들이 꼭 정렬되어야 한다는 것!!

 

따라서 코드를 작성할 때 정렬된 배열이 주어진 것이 아니라면, 미리 arr.sort를 해주는 것이 필요하다.

let arr = [2, 4, 7, 20, 12, 6, 21, 692, 3];

위에 예시로 들었던 코드를 통해 이진검색 코드를 구현해보려 한다.

let findArr = arr.sort((a, b) => a - b);

먼저 주어진 배열을 오름차순으로 정렬해준다.

이진 검색은 두 개의 포인터를 사용한다. 보통 이 포인터들을 left, right로 명명하겠다. 이름 그대로 왼쪽 부분에 존재하는 포인터와 오른쪽 부분에 있는 포인터를 가리킨다. 이렇게 설정한 포인터들이 위치하는 배열의 인덱스값을 사용하여 배열의 중앙 인덱스값을 구한다. 

function binarySearch(array, targetValue) {
    let left = 0;
    let right = array.length - 1;
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        if(array[mid] === targetValue) {
            return array[mid];
        }
        else if(array[mid] > targetValue) {
            right = mid - 1;
        }
        else if(array[mid] < targetValue) {
            left = mid + 1;
        }
    }
    return -1;
}

left를 배열의 첫 인덱스 그리고 right를 마지막 인덱스를 할당하여 초기값을 설정해주고, 그 후 해당 인덱스값을 이용하여 중간 인덱스값인 mid를 구해준다. 만일 mid 인덱스에 저장된 값이 targetValue와 동일하다면 함수가 종료되지만, 그렇지 않은 경우 mid 인덱스에 저장된 값과 targetValue를 비교하여 만일 mid 인덱스에 저장된 값이 크다면 mid 인덱스값에 -1을 하여 right 포인터에 할당해준다.

만일 mid 인덱스에 저장된 값이 targetValue보다 작다면 mid 인덱스값에 +1을 하여 left 포인터에 할당해준다.

위의 연산을 left가 right보다 커지는 경우까지 반복한다. 그리고 만일 찾지 못한다면, index 내부에 값이 없다는 것을 알려주기 위해 -1을 반환해준다.

 

1. 같을 경우 → 탐색을 원하는 값을 반환하고 탐색 종료
2. mid 인덱스의 요소 > 탐색하는 값 → right의 값을 미드보다 1작은 값으로 설정(right = mid - 1)
3. mid 인덱스의 요소 < 탐색하는 값 → left의 값을 미드보다 1 큰 값으로 설정(left = mid + 1)
4. index 내부에 존재하지 않은 경우 → -1을 리턴