면접질문 알고리즘

1. 이진탐색

이진탐색은 탐색범위를 반씩 줄여서 검색하는 방법이다.

T(N) = O(log2(N))

// pseudo code
1. min = 1, max = n

2. mid = Math.floor((min + max) / 2)

3. 탐색

4. mid가 타겟일 경우 종료

5. mid가 타겟보다 작을 경우 min = ++mid 후에 2, 3 반복 (min < max 일때)

6. mid가 타겟보다 클 경우 max = --mid 후에 2, 3 반복 (min < max 일때 )

7. min >= max보다 큰 경우 탐색 종료. 1을 더하거나 빼기 이전 mid 값 반환

2. 트리자료구조

트리는 인접리스트와 인접 배열로 구현할 수 있다.

3. 탐색종류