Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- GIT
- 수치최적화
- Frenet Coordinate
- C++
- C
- 동적라이브러리
- Hybrid A star
- GNN
- 공유라이브러리
- Motion Planning
- 정적라이브러리
- OSQP
- 소프티어
- 백준
- Recursion
- DynamicProgramming
- autonomous vehicle
- MDP
- self driving car
- CPP
- Leetcode
- CUDA
- 선형대수
- Graph Neural Network
- 경로생성
- PathPlanning
- path planning
- 강화학습
- solver
- Dubins Path
Archives
- Today
- Total
Swimmer
이진 검색 알고리즘 (Binary Search Algorithm) 본문
이진 검색 알고리즘 (Binary Search Algorithm)
- 오름차순 (혹은 내림차순)으로 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘
- 시작과 마지막 범위 내에서 중간의 값을 임의로 선택하여 찾고자 하는 값과 비교
- 중간 값이 찾는 값 대비 작다면, 시작 범위를 중간 값으로 설정
- 중간 값이 찾는 값 대비 크다면, 마지막 범위를 중간 값으로 설정
장점
- 특정 값을 찾기 위해 배열의 모든 인덱스를 모두 탐색하는 것 대비, 탐색 범위를 절반씩 줄여나가기 때문에 속도가 빠르다.
단점
- 배열이 정렬되어 있어야 한다.
- 정렬을 위한 연산이 소요 된다.
적용 문제 예시
- 배열 내에서 Target 값과 가까운 3개의 원소를 찾는 문제
- 모든 원소를 탐색하면 O(n^3)의 Time Complexity인데, 이진 탐색 알고리즘을 사용하면 O(n^2)으로 줄일 수 있다.
- ex) Leet Code 16. 3Sum Closest
'개념공부 > 알고리즘' 카테고리의 다른 글
Backtracking Algorithm (0) | 2023.03.09 |
---|---|
Binary Tree Traversal, Binary Tree (1) | 2023.03.07 |
Trie 자료 구조 (0) | 2023.01.25 |
Dijkstras Algorithm (다익스트라 알고리즘) (0) | 2023.01.15 |
Pure Pursuit <Path Tracking Algorithm> (0) | 2022.05.24 |
Comments