728x90
안녕하세요. 개발감자 박그냥입니다!🥔
오늘은 알고리즘 중 이진탐색에 대해서 정리해보도록 하겠습니다.
1. 이진탐색
- 기능 : 데이터가 정렬되어 있는 상태에서 타킷 데이터를 탐색하는 알고리즘
- 특징 : 중앙값 비교를 이용해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다. 이분탐색이라고도 불립니다.
- 시간 복잡도 : O(logN) ->> N : 데이터의 갯수
2. 이진탐색의 원리
일단, 데이터가 오름차순으로 정렬되어 있어야 합니다! ( 만약 내림차순이라면 조건을 반대로 설정하세요)
저는 타깃데이터가 16이고, 1,4,6,7,9,14,16으로 정렬되어 있는 데이터를 가지고 원리를 설명해보도록 할게요 !
1) 현재 데이터셋의 중앙값을 선택합니다.
- 이 데이터 셋의 중앙값인 7을 선택했습니다.
2) 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터 셋을, 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택합니다.
- 위의 사진에서 중앙값이 7이었고 타깃 데이터는 16이기 때문에 오른쪽 데이터 셋인 9,14,16을 선택했습니다.
- 현재 중앙값이 14이고 타깃데이터가 16이기 때문에 14의 오른쪽 데이터셋인 16을 선택할 것입니다.
3) 2번의 과정을 반복하다가 중앙값 == 타깃 데이터 일 때 탐색을 종료합니다.
3. 이진탐색 활용
- 코딩 테스트에서 원하는 데이터를 탐색할 때 가장 일반적으로 사용되는 알고리즘으로, 구현 및 원리가 비교적 간단합니다.
더 유익한 포스팅으로 돌아올게요! 개발감자였습니다 :)
728x90
반응형
'알고리즘' 카테고리의 다른 글
| [알고리즘 마스터] 9. 그래프 알고리즘 정리 (유니온 파인드, 위상정렬, 최단거리 알고리즘) (1) | 2023.12.29 |
|---|---|
| [알고리즘 마스터] 8. 그리디 알고리즘 (Greedy) (1) | 2023.12.28 |
| [알고리즘 마스터] 6. BFS (너비 우선 탐색) (1) | 2023.12.27 |
| [알고리즘 마스터] 5. DFS (깊이 우선 탐색) (2) | 2023.12.27 |
| [알고리즘 마스터] 4. 그래프 이론 (개념 및 표현) (0) | 2023.12.26 |
