[Algorithm] Binary Search 의 간단한 구현 (C++)
알고리즘2023. 5. 26. 12:08[Algorithm] Binary Search 의 간단한 구현 (C++)

Linear Search 보다는 상대적으로 복잡하지만 자료구조의 원소가 "정렬"되어 있을 경우 O(log n)으로 동작하는 이진 탐색을 반복문과 재귀함수로 구현해보도록 하겠습니다. 먼저 이진탐색의 로직은 정렬되어 있는 데이터의 첫번째 부분 first, 데이터의 마지막 원소 last 인덱스를 구한뒤 (first + last) / 2를 통해 mid인덱스를 구합니다. (나머지는 버립니다) 이후 mid인덱스에 들어 있는 값이 찾을려고 하는 값과 같다면 그대로 값을 찾은 것이고 찾을려고 하는 값이 mid인덱스에 들어있는 값보다 작다면 last를 mid - 1로 변경한뒤 first와 last를 다시 합한뒤 2로 나누어 mid를 다시 구해 줄 수 있습니다. 종료 조건은 first가 last보다 클 경우 입니다. fi..

image