이진 탐색 - 간단하고 강력한 탐색 알고리즘 ( 1 )

오늘 포스팅할 이진 탐색은 간단하면서도 강력한 알고리즘 중 하나입니다.
이러한 점 때문에 많은 알고리즘 서적에서 초반부에 등장하여 알고리즘이란 무엇인가를 보여주는 유명한 알고리즘입니다.
그러면 우리도 이번 포스트에서 함께 이진 탐색 알고리즘의 강력함을 느껴보겠습니다.

---

1. 정렬된 배열 ( Ordered Array )

 머릿말에 이진 탐색을 알아보자는 말을 하고서는 갑자기 웬 배열이냐고 하실 수 있습니다. 갑자기 출현하게 된 이유는

이진 탐색 알고리즘은 정렬된 배열에 대해서만 적용할 수 있는 알고리즘 이기 때문입니다.

정렬된 배열은 일반적인 배열과 거의 동일 합니다. 유일한 차이는 이름에서 알 수 있듯이 값이 항상 순서대로 있어야 한다는 점뿐입니다. 이 규칙성을 지키기 위해 삽입 연산이 이루어질 때에도 적절한 위치에 넣어주어 값이 정렬된 상태를 유지해 주어야만 합니다.

---

2. 정렬된 배열의 삽입 연산

 정렬된 배열의 삽입 연산 단계를 살펴보겠습니다.

우선  시작 인덱스부터 마지막 인덱스로 이동하며  자신보다 큰 최초의 원소 위치를 탐색 합니다.

 

 

찾은 이후 삽입을 위해 뒤에 위치한 원소들 ( 삽입하려는 원소보다 큰 )을 1칸씩 이동시킵니다.

 

 

해당 자리에 원소를 삽입합니다.

 

이렇게 하면 배열의 정렬을 지킨 채로 새로운 원소의 삽입을 해냈습니다.

 단계를 계산해 보면 크기가 N인 배열에서 삽입하려는 원소보다 큰 원소들이 x ( x > 0 ) 개 존재 할 때에

• 자신보다 큰 원소가 최초로 발견되는 위치 탐색 : N - x + 1 단계
• 빈 공간 생성 위하여 삽입하려는 원소보다 큰 원소들을 1 인덱스 뒤로 이동 : x 단계
• 원소삽입 : 1 단계

총 N + 2 단계에 걸쳐 이뤄지게 됩니다.

삽입 연산으로 비교하여 보았을 때 일반적인 배열에서 N + 1 단계가 소모되었다면 정렬된 배열에서는 N + 2로 조금 더 많은 비용이 든다는 것을 알 수 있습니다. 그렇다면 비용이 더 많이 드는 정렬된 배열을 왜 사용할까요?

---

3. 정렬된 배열의 탐색

 배열에 존재하지 않는 값을 탐색하는 상황을 가정하고 일반 배열과 정렬된 배열에서 어떠한 일이 발생하는지 보겠습니다.

일반 배열은 진행 도중 해당 원소를 발견하지 못한다면 현재 위치보다 뒤에 찾는 값이 존재할 수 있기에 항상 배열의 마지막 원소까지 탐색을 해야만 합니다.

 

7 을 못찾는다면 배열의 마지막 원소까지 탐색

 

그렇다면 정렬된 배열에서는 어떨까요?

배열의 탐색을 진행 도중 찾는 값보다 큰 값을 만난다면 해당 배열에 찾고자 하는 값이 존재하지 않을 것이라는 것을 인지하고 그 즉시 탐색을 종료할 수 있습니다.

 

8 을 만나는 순간 배열에 찾는 값이 없는것을 인지 하고 탐색 종료

코드로 구현해 본모습은 어떨까요?

// 배열 arr은 반드시 정렬된 배열
function searchInOrderedArray(arr, searchValue) {
    for (let i = 0; i < arr.length; i++) {
    // 찾고자 하는 값 발견 시 인덱스 반환
        if(arr[i] === searchValue) {
            return i;
    // 탐색 중 찾고자 하는 값보다 큰 값 확인 시 즉시 종료
        }else if(arr[i] > searchValue) {
            break;
        }
    }
    return null;
}

 

마치며

이번 포스트는 어떠셨나요?
자료가 어떠한 규칙성을 가지고 담겨있다는 것만으로도 연산이 동작하는 방법이 너무 신기하지 않나요?
하지만 아직 힘을 다 보여주지 않았습니다.
다음 포스트에서는 원래 소개드리고자 했던 "이진 탐색"으로 이어가겠습니다.

 

관련글

이진 탐색 - 간단하고 강력한 탐색 알고리즘 ( 2 )