이진 탐색(Binary Search) - 정의 / 예시 코드(C++)

 

이진 탐색은 정렬된 배열에서 특정한 값을 찾는 알고리즘으로, 탐색 범위를 반씩 줄여가며 원하는 값을 찾아내는 방법입니다. 이 알고리즘은 배열이나 리스트 등의 데이터 구조에서 효율적인 탐색을 수행할 수 있습니다.

이진 탐색의 동작 원리는 다음과 같습니다.

 

 

1. 주어진 배열을 오름차순으로 정렬합니다.

 

2. 탐색할 값과 배열의 중간 값을 비교합니다.
   - 중간 값이 탐색할 값과 일치하면 탐색 성공입니다.
   - 중간 값이 탐색할 값보다 크면, 배열의 왼쪽 절반에 대해 이진 탐색을 수행합니다.
   - 중간 값이 탐색할 값보다 작으면, 배열의 오른쪽 절반에 대해 이진 탐색을 수행합니다.

 

3. 탐색 범위가 축소될 때까지 위의 과정을 반복합니다.

 

4. 탐색 범위가 더 이상 없거나, 탐색할 값이 발견되지 않으면 탐색 실패입니다.

 

 

이진 탐색의 시간 복잡도는 O(log n)으로 매우 효율적입니다. 탐색 범위가 반씩 줄어들기 때문에 데이터 크기에 비례하여 탐색 시간이 증가하지 않습니다.

 

반응형

이제 C++로 이진 탐색을 구현한 예시 코드를 살펴보겠습니다.

 

 

위의 예시 코드에서는 주어진 오름차순으로 정렬된 배열에서 탐색할 값을 이진 탐색으로 찾는 함수 binarySearch를 구현하였습니다. binarySearch 함수는 배열, 탐색할 값, 그리고 탐색 결과로 타겟 값의 인덱스를 반환합니다. main 함수에서는 예시로 정수형 배열과 탐색할 값을 설정하고, 이진 탐색 결과를 출력합니다.

이진 탐색은 정렬된 데이터에서 빠른 탐색을 수행하는 강력한 알고리즘입니다. 크기가 큰 데이터 집합에서 효율적인 탐색을 위해 이진 탐색을 활용할 수 있습니다.