이진 탐색
이진 탐색(Binary Search)
이진 탐색은 정렬된 배열에서 데이터를 탐색하는 알고리즘
시간 복잡도: O(logN)
배열의 중앙에 있는 임의값을 찾은 뒤, 탐색할 수와 비교를 한다.
만약 임의의 중간값보다 탐색하고자 하는 수가 크면 배열의 우측을 대상으로 다시 탐색하고, 중간값보다 탐색하고자 하는 수가 작으면 배열의 좌측을 대상으로 탐색한다.
배열이 정렬되어 있다는 것을 활용해서 탐색할 범위를 매번 반씩 줄여나갈 수 있다.
장단점
- 장점
- 탐색이 반복될 때마다 목표값을 찾을 확률은 두배가 되므로 속도가 빠름
- 단점
- 정렬된 리스트에서만 사용할 수 있음
이진 탐색(Binary Search) js 코드
const binarySearch = (array, number) => {
let start = 0,
end = array.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (array[mid] === number) return mid;
if (array[mid] < number) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
};