목록2024/08/14 (1)

말감로그

24.08.14 알고리즘 - 이진 탐색(Binary search)

이진 탐색(Binary search)이진 탐색은 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 시간 복잡도 : O(logN) 1. 배열을 오름차순으로 정렬한다.2. 배열의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.3. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.    ⓐ target이 mid 값보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)    ⓑ target이 mid 값보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색) def binary_search(targe..
TIL 2024. 8. 14. 16:59
이전 Prev 1 Next 다음