이진 탐색 알고리즘(Binary Search Algorithm)

• Binary Search Algorithm 은 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘이다.

알고리즘이 동작하는 단계는 아래와 같다.

1. 정렬된 배열의 가장 중간 인덱스를 지정한다.
2. 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료한다. 아니라면 3단계로 간다.
3. 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다.
4. 값이 있는 부분과 값이 없는 부분으로 분리한다.
5. 값이 있는 부분에서 다시 1단계부터 반복한다.

---

• Binary Search Algorithm 은 데이터를 찾을 때 사용하는 방법으로, 주로 아래의 경우에 사용한다.

1. 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용한다.
2. 데이터의 양이 많으면 많을수록 효율이 높아서 정렬된 데이터의 양이 많을 때 사용한다.
3. 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가지게 된다.

• 시간복잡도는 O(logn)로, 빠른 편이지만 항상 효율이 좋은 것은 아니다.

• 데이터양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm 이 빠른 구간이 존재한다. 순차 검색 알고리즘(sequential search algorithm) 또는 선형 검색 알고리즘(linear search algorithm) 은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다.

• Binary Search Algorithm이 효율적인 만큼 한계도 명확하다.

  • 배열에만 구현할 수 있다.
  • 정렬되어 있어야만 구현할 수 있다.
  • 규모가 작은 배열이라도 정렬이 되어 있지 않다면 정렬을 한 후 Binary Search Algorithm 을 사용해도 효율이 높지 않다.

---

용례

Binary Search Algorithm 은 대규모의 데이터 검색에 주로 사용한다.

• 사전 검색
  • 사전에서 단어를 찾을 때 사용
• 도서관 도서 검색
  • 도서관에서 사용하는 도서 코드로 도서를 검색할 때 사용
• 대규모 시스템에 대한 리소스 사항 파악
  • 시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU 양에 대해서 파악할 때 사용
• 반도체 테스트 프로그램은 디지털, 아날로그 레벨을 측정하는데 Binary Search Algorithm을 사용

추가 공부할 키워드

• Linear Search Algorithm
• Hash Search Algorithm
• Divide-and-conquer algorithm
• Binary Tree vs Binary Search Tree
• Binary Search Algorithm vs Binary Search Tree