이진 탐색이란?
이진 탐색 (Binary search)
이진 탐색은 정렬 된 데이터 배열에 특정 값을 찾아내는 알고리즘이다.
중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교 후 X가 중간값보다 작으면 중간값 기준 좌측, X가 중간값 기준으로 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하여 비교한다.
해당 값을 찾을때까지 이 과정을 반복한다.
위 그림을 보면 오름차순으로 정렬된 배열에서 Target(22)를 찾는 이진 탐색을 시작한다. 탐색을 반복적으로 수행하여 마지막 22 타겟을 찾는다.
시간복잡도 : O(logN)
해당 알고리즘은 반복문과 재귀 두가지 방법으로 구현이 가능하다.
'Coding Test' 카테고리의 다른 글
백준 듣보잡(1764) (0) | 2024.02.27 |
---|---|
백준 카드2(2164) (0) | 2024.02.27 |
백준 수 정렬하기 2(2751) (1) | 2024.02.27 |
백준 숫자 카드(10815) (1) | 2024.02.26 |
시작 (0) | 2024.02.25 |