[데브코스 7일차] 이진 탐색 + 1주차 회고

🤔 생각해볼 것

1. 이진 탐색과 이진 탐색 트리의 차이는 무엇일까요?

2. 이진 탐색은 정렬되지 않은 배열에서 사용할 수 있을까요?

3. 이진 탐색 알고리즘을 반복문으로 구현해보세요.

4. 이진 탐색 알고리즘을 재귀로 구현해보세요.

5. 이진 탐색 트리를 구현해보세요.

 

[1] 이진 탐색과 이진 탐색 트리의 차이

이진탐색트리(Binary-Search-Tree)와 이진검색(Binary-Search)의 개념적 차이

 1) 이진탐색트리(BST)는 정렬된 구조를 저장하고 탐색하는 "자료구조"이고, 이진검색은 정렬된 배열에서 값을 찾아내는 "알고리즘" 그 자체를 지칭.

2) 보통 투포인터나 재귀를 통해 구현을 한다.

 

[2] 선형 탐색과 이진 탐색

선형 탐색

데이터가 정렬되어있지 않다면 완전 탐색을 할 수 밖에 없다. 시간복잡도 O(N)

이진 탐색

로그는 마법과도 같다. 데이터가 정렬되어 있다는 가정하에, 10만개의 데이터 중에서 원하는 값을 찾기 위해서는 최대 단 16번의 연산만 수행하면 된다. 시간복잡도 O(logN)

 

💡 과제로 너무나 바빴던... 분노의 회고(일기)

내 자신한테 화난 것임...ㅜㅜ

https://ryong9rrr.notion.site/67c1976dfe864a538d1d98b769789364

과제로 불태운 하루(일기)