목록이진탐색 알고리즘 (1)

Jaeilit

이진탐색

완전탐색 중 단순 브루트포스는 모든 값을 읽어내기 때문에 가장 오래걸리지만 가장 확실한 방법입니다. 주어진 배열에서 어떤 값을 비교해서 최대 값을 찾거나 최소 값을 찾거나 이런 경우에는 배열을 2중으로 훑어야 하기 때문에 시간 복잡도는 O(n^2) 이 됩니다. 이진탐색 나무위키 그림입니다. 기본개념은 분할정복인데, 이유는 계속 반으로 나누면서(분할) 내가 원하는 조건에 상회하는지 지속적으로 살피는 것이기 때문이다. 이진탐색의 시간복잡도는 O(log N)으로 선형탐색 O(N) 보다 더 빠릅니다. 이유는 정말 간단하게도 분할을 하기 때문입니다. 이진탐색의 예시 코드 입니다. left 또는 statrt 라고 표현하며 시작 지점과, rigth 또는 End 라고 표현하는 끝 지점을 지정해주고 middle 지점은 ..
알고리즘 2022. 9. 17. 14:33
이전 Prev 1 Next 다음