정의
이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.
조건
이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다.
과정
start, end, mid의 변수 3개를 사용하여 탐색을 수행하고, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾습니다.
시간복잡도
| O(log N) |
단계마다 탐색 범위를 반으로 나누는 것 "÷2" 과 동일하므로 O(logN)의 시간복잡도를 갖습니다.
구현
이분탐색을 반복문 혹은 재귀함수로 직접 구현할 수도 있고, C++의 lower_bound 함수를 사용할 수도 있습니다.
(자세한 사용 방법과 예시는 아래 코딩테스트 문제를 풀었을 때의 내용을 참고)
2023.08.10 - [💻코딩테스트/백준] - [백준/C++] 12015번 : 가장 긴 증가하는 부분 수열 2 (LIS 수열 문제)
[백준/C++] 12015번 : 가장 긴 증가하는 부분 수열 2 (LIS 수열 문제)
가장 긴 증가하는 부분 수열 2 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분
cse-child.tistory.com
참조
[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)
이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는
velog.io
'👩🏻💻기초지식 > CS' 카테고리의 다른 글
| [OS] 프로세스와 멀티 프로세스, 스레드와 멀티 스레스 (0) | 2023.10.23 |
|---|---|
| [자료구조] 이진 탐색 트리 (BST, Binary Search Tree) (0) | 2023.10.03 |
| [알고리즘] 정렬 알고리즘 8가지 (0) | 2023.10.02 |
| [네트워크] OSI 7 계층과 TCP/IP 4 계층, 계층 별 PDU (0) | 2023.09.14 |
| [OS] 메모리 단편화 (0) | 2023.09.11 |