이진 탐색 / 매개 변수 탐색
1. 선형 탐색보통 생각하는 탐색(완전 탐색)은 선형 탐색으로 수행된다.예를 들어 어떤 수(10)가 배열에 존재 하는지 탐색하는 상황을 말한다.선형 탐색은 일렬된 자료를 단방향으로 모두 확인하며 탐색을 진행하기 때문에 시간복잡도는 O(n)이 나온다.만약, 배열이 정렬이 되어 있다면 더 빠르게 탐색할 수 있다.정렬이 기본적인 전제 조건으로 배열이 있다면?2. 이진 탐색정렬된 상태의 배열에서의 탐색 (10을 찾기)이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색을 진행어떤 수를 찾을 때, 범위를 절반씩 줄여나가며 정답 후보를 갱신하므로 시간복잡도는 O(logN)이 나온다.ex) [1, 6, 8, 10, 15, 16, 20, 22, 23, 24] - 배열 내 10을 찾는 과정start 1 ~ end 24 → m..
2024. 8. 12.
