[Algorithm] 이진 탐색(Binary Search, 이분 탐색, 이진 검색)

이진 탐색(Binary Search)

정렬된 데이터 집합을 이분화하면서 특정한 값을 탐색하는 검색 알고리즘 

-> 자료들이 순서대로 정리되어 있을 때 원하는 값을 찾기 위해 자료를 반씩 나누어 살펴보는 방법

 

시간 복잡도가 O(logN)으로 대표적인 로그 시간 알고리즘

 

1) 특정한 값을 찾기 위해 정렬된 데이터 집합의 중간 값 X와 비교한다. 
2) X보다 작으면 X를 기준으로 왼쪽 데이터들, X보다 크면 X를 기준으로 오른쪽 데이터들 대상으로 다시 탐색한다. 
3) 1 - 2번을 반복하며 특정값을 찾을 때 까지 반복한다.   

 

 

 

 

종료 조건 : 원하는 값을 찾으면 종료

 

하지만 원하는 값이 배열에 존재하지 않는다면 탐색을 하다가 찾지 못했는데 더 이상 남은 배열이 존재하지 않으면 원하는 값이 배열에 존재하지 않는다고 판단하고 종료된다. 

 

 

 

---

정보 출처 및 참고

이진 탐색