이진 검색이란?
검색할 데이터 열이 정렬되어 있다면, 이진 검색으로 원하는 데이터를 빠르게 찾을 수 있다.
시간 복잡도 O(logn)
N: 데이터 개수, T: 찾고자 하는 값, M: 중앙 위치
1 단계: 중앙 위치 M을 N/2로 만든다.
2 단계: 검색 범위 안의 데이터 개수가 1개 이상이라면 다음 3단계를 반복한다.
3 단계:
T = DATA[M]일 때: 데이터를 찾았으므로 반복 중단
T < DATA[M]일 때: DATA[M] 및 DATA[M]의 오른쪽(큰 값)에 데이터 T는 절대
존재하지 않으므로, 검색 범위를 위치 M보다 왼쪽(작은 값)으로 좁힌다.
T > DATA[M]일 때: DATA[M] 및 DATA[M]의 왼쪽(작은 값)에 데이터 T는 절대
존재하지 않으므로, 검색 범위를 위치 M보다 오른쪽(큰 값)으로 좁힌다.
function solution(target, arr) {
let answer;
arr.sort((a, b) => a - b);
let lt = 0;
let rt = arr.length - 1;
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2, 10);
if (arr[mid] === target) {
answer = mid + 1;
break;
} else if (arr[mid] > target) rt = mid - 1;
else lt = mid + 1;
}
return answer;
}
let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));