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

이진 탐색 알고리즘

이진 탐색 알고리즘의 동작 단계

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

위 과정에 따라 특정한 값 찾아보기

• 1 step - 찾으려는 182가 중간 인덱스 67보다 크기 때문에 67보다 큰 부분을 새로운 범위로 설정하여 다시 찾기
• 2 step - 찾으려는 182가 1 step의 큰 부분의 중간 인덱스 127보다 크기 때문에 127보다 큰 부분을 새로운 범위로 설정하여 다시 찾기
• 3 step - 찾으려는 182가 2 step의 큰 부분의 중간 인덱스 182와 같으므로 탐색 종료
• 같은 값을 Linear Search Algorithm으로 찾아본다면 11번의 과정이 필요함

이진 탐색 알고리즘 사용 경우

• 정렬된 배열에서 요소값을 더 효율적으로 검색할 때 사용
• 데이터의 양이 많으면 많을수록 효율이 높아서 정렬된 데이터의 양이 많을 때 사용

탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가짐

• 시간 복잡도는 O(log n)로, 빠른 편이지만 항상 효율이 좋은 것은 아님
  - 데이터 양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 빠른 구간이 존재함

• Binary Search Algorithm
  

• Linear Search Algorithm

이진 탐색 알고리즘의 한게

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

Binary Search Algirthm 사용

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

Binary Search Tree(BST)와 다른점

Tree는 자료구조를 나타내고, Algorithm은 해결 방법을 나타냄.
Binary Search Tree는 하나의 노드가 두 개의 하위 트리를 가지는 이진 트리로 이루어진
자료구조.

BST의 규칙

• 부모 노드는 왼쪽 자식노드보다 큰 값을 가짐
• 부모 노드는 오른쪽 자식노드보다 작은 값을 가짐