'탐색' 태그의 글 목록

[Algorithm]이진탐색(Binary Search)

이진탐색(Binary Search) 정렬된 상태의 입력 데이터에 대한 효과적인 탐색 방법 오름차순 탐색 방법 배열의 가운데 원소 A[x]와 탐색키 y를 비교. 1) 탐색키 = 가운데 원소 -> 탐색 성공(인덱스 x)를 반환 후 종료 2) 탐색키 '이진 탐색(원래 크기 1/2인 왼쪽 부분 배열) ': 순환호출 3) 탐색키 '이진 탐색(원래 크기 1/2인 오른쪽 부분 배열) ': 순환호출 예제 T(n) = T(n/2) + O(1) (n > 1), T(1) = 1 T(n) = O(logn) 특징 배열의 데이터가 정렬된 경우에만 적용. 삽입 / 삭제 연산은 부가적인 데이터 이동을 수반. 데이터의 정렬 상태 유지를 위해서 평균 n/2개의 데이..

CS 2022.02.24

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Bangta's quantum

탐색 1

티스토리툴바