728x90
✍️ 정의
이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복잡도가 순차적 탐색보다 낮다.
🆚 순차적 탐색 vs 이분 탐색
순차적 탐색
- 정렬된 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 차례로 탐색
이분 탐색
- 정렬된 배열 안에서 특정 원소를 찾을 때, 인덱스 left와 right의 중간값과 비교
- 중간값과 비교해서 찾는 원소가 아니면 인덱스 left 또는 right를 다시 정해준다.
- 인덱스 left와 right를 정할 때마다 탐색 범위는 반으로 줄어든다.
🔎 이분 탐색 방법
- 처음 범위는 인덱스 left = 0, right = 끝, mid = (left + right) / 2
- mid의 값과 찾는 원소를 비교한다.
- mid == 찾는 원소이면, 탐색 종료
- mid < 찾는 원소이면, left = mid + 1 로 하여 다시 반복
- mid > 찾는 원소이면, right = mid - 1 로 하여 다시 반복
- 만약 left > right 가 된다면, 해당 배열에는 찾는 원소가 없다.
⏰ 시간 복잡도
순차적 탐색 ( O(n) )
- 최악의 경우, 배열의 끝까지 탐색해야 한다.
이분 탐색 ( O(log n) )
- 범위를 새로 정할 때마다 탐색 범위는 1/2씩 줄어든다.
인용
[알고리즘/Java] 이분 탐색 / 이진 탐색 (Binary Search)
이분 탐색이란?이분 탐색 방법이분 탐색 구현(Java)시간복잡도이분 탐색은 이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복
velog.io
728x90
