이진검색(+복잡도)

이진 검색

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

방법

1. (정렬된) 배열의 중앙에 위치한 요소를 검색하여 원래 검색하려는 값과 크기를 비교한다.
2. 만약 값이 크다면, 중앙값 다음 순서부터 끝까지 배열의 중앙 값을 찾는다. 그리고 원래 검색하려는 값과 비교한다.
3. 그렇게 검색 범위를 한 번에 절반씩 좁혀나간다.
   1. 중앙값이 검색하려는 값과 일치하거나
   2. 검색 범위가 더 이상 없는 경우 알고리즘을 종료한다.

이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다.

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다. 복잡도는 아래의 두 가지 요소를 가지고 있다.

1. 시간 복잡도: 실행에 필요한 시간을 평가한 것.
2. 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것.

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 복잡도를 우선한다. 즉 전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.
예를 들어 이진 검색법을 이용하면 검색할 요소의 범위를 절반씩 좁힐 수 있다. 이에 이진 검색 알고리즘의 복잡도를 구하면 아래처럼 O(log n)을 얻을 수 있습니다.

 

---

출처:

1. 책 <자료구조와 함께 배우는 알고리즘 입문 자바편>