목록O(log n) (1)

포시코딩

이진 탐색(Binary Search), 시간 복잡도 O(log N)

2진 탐색 인덱스가 0부터 16까지 있는 array가 있을 때 그 중 정답이 target인 값을 찾으려면 어떻게 해야할까? for문을 통해 처음부터 하나씩 비교하는 방법이 있겠지만 맨 마지막에 정답이 있으면 O(N) 만큼의 시간 복잡도가 걸리게 될 것이다. 이 때, 2진 탐색이라는 방법을 통해 시도 횟수를 확 낮출 수 있다. 딱 가운데 위치하는 값을 정답과 비교해서 정답이 더 크다면 가운데 위치하는 값 이하의 인덱스를 모두 버리고 정답이 더 작다면 가운데 위치하는 값 이상의 인덱스를 모두 버리는 식으로 구하며 이를 반복하면 된다. 이는 알고리즘 문제에서 UP & DOWN 문제로도 자주 나오는 형태이다. 문제풀이 예시 시간 복잡도 O(log N) 총 숫자가 1 ~ N 까지라고 한다면 1번 탐색하면 반절이 ..
자료구조알고리즘/이론 2022. 11. 24. 14:12
이전 Prev 1 Next 다음