이분 탐색
Binary Search
탐색 범위를 반으로 나누어 원하는 값을 탐색하는 알고리즘
분할 정복 기법의 응용으로 배열이 정렬되어 있을 때만 사용이 가능하다.
Process
1.
먼저 배열을 정렬한다.
2.
배열을 반으로 나누어 왼쪽 구역, 오른쪽 구역으로 나눈다.
3.
중간 값과 찾으려는 값을 비교했을 때, 찾으려는 값이 더 작으면 왼쪽구역에서 찾으려는 값이 더 크면 오른쪽 구역에서 2-3번 과정을 반복한다.
python
def binary_search(arr, item):
left = 0
right = len(arr) - 1
while left <= right:
midpoint = (left + right) // 2
if arr[midpoint] == item:
return midpoint
else:
if item < arr[midpoint]:
right = midpoint - 1
else:
left = midpoint + 1
return None
Python
복사
JavaScript
function binarySearch(arr, item) {
arr.sort((a, b) => a - b);
let left = 0, right = arr.length;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (item === arr[mid]) return mid;
if (item < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return undefined;
}
JavaScript
복사
•
시간복잡도 : O()
•
공간복잡도 :
장점
•
선형 탐색에 비해 빠른 시간에 정렬할 수 있다.
단점
•
정렬된 배열에서만 사용할 수 있다.