출처 사이트로 이동 : penjee.com
정렬된 배열에서 특정 값을 찾는 알고리즘으로 배열의 중간을 기준으로 데이터를 탐색하기 때문에
반드시 데이터가 정렬된 상태로 존재해야 탐색을 할 수 있습니다
중간을 기준으로 탐색 대상을 절반씩 줄여가는 탐색 알고리즘으로 O(logN) 시간복잡도를 가집니다
arr
에서 target
의 인덱스를 반환하는 코드입니다
const binarySearch = function (arr, target) {
const search = function (start, end) {
let mid = parseInt((start + end) / 2);
if (start === end) {
return arr[mid] === target ? mid : -1;
}
if (target > arr[mid]){
return search(mid + 1, end);
} else if (target =< arr[mid]) {
return search(0, mid);
}
}
}
return search(0, arr.length - 1);
};
1. let mid = pasrseInt((start + end) / 2);
변수 mid
에 첫번째 인덱스와 마지막 인덱스의 중간 인덱스를 할당
2. 재귀탈출 조건
재귀를 통해 계속해서 배열의 길이 / 2
첫번째 인덱스와 마지막 인덱스가 같아질때
즉, arr.length
가 1이 될 때 arr[start] === target
을 만족할 경우 start
반환 아닐 경우 -1
반환
if (start === end) {
return arr[start] === target ? start : -1;
}
3. target
과 arr[mid]
비교
target
> arr[mid]
arr
의 start = mid + 1
, end = end
로 다시 search 함수의 인자로 들어갑니다
target
<= arr[mid]
arr
의 start = 0
, end = mid
로 다시 search 함수의 인자로 들어갑니다
4. return search(0, arr.length -1);
arr
의 0번째 인덱스
와 마지막 인덱스
를 인자로 받는 함수를 리턴하도록 합니다
➡️ 탈출조건을 만족할 때 까지 search(start, end)
함수를 재귀로 반복합니다.