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

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

이진 탐색 알고리즘 동작 원리

Up&Down 게임과 흡사하다

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

장점 ( 주 사용처)

사전 검색, 도서관 도서 검색, 대규모 시스템에 대한 리소스 사항 파악 등

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

 

단점

• 시간복잡도는 O(log n)으로 빠른 편이지만 항상 효율이 좋은 것은 아님
  • 데이터양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 빠른 구간이 존재한다
• 배열에만 구현할 수 있다
• 정렬되어 있어야만 구현할 수 있다