목록2024/03 (1)
개발하는 리프터 꽃게맨입니다.
[C++/알고리즘] 이진탐색
이진 탐색 알고리즘은 '정렬된 상태의 배열' 에서 원하는 값을 O(log n) 만에 탐색할 수 있는 알고리즘 입니다. 그 방법은 '업앤다운 숫자맞추기'를 하는 방법과 유사합니다. 1~50 중에서 상대방이 생각한 숫자를 가장 빨리 맞추는 방법은 절반인 25를 말해서 업, 다운을 듣고 업! 이라면 37 다운! 이라면 12 을 말하면서 점차 줄여나가는 방식입니다. 계속 절반 절반 반띵하면서 원하는 수를 찾아가는 것이죠. 샘플코드 입니다. 찾고자 하는 값이 mid 값보다 크냐 작냐에 따라서 찾고자하는 범위를 좁혀나가는 것입니다. 재귀적으로 코드를 구성할 수 있습니다. 이진탐색의 경우 log2 N 의 시간복잡도를 가지며, 임의 접근이 불가한 연결리스트의 경우에는 설사 정렬이 되어 있더라도 이진 탐색을 사용할 수 ..
알고리즘/알고리즘 이론
2024. 3. 21. 13:09