JS 알고리즘 노트 (이진탐색)
기본 로직
배열이 주어지면 그걸을 반으로 나누어 범위를 좁혀 찾아보고
범위 안에 없으면 범위 값 기준으로 배열을 다시 반으로 나누어 찾아보는 구조
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 = Math.floor((lt+rt)/2)
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));
해설 :
1. 이진탐색을 하기 위해서는 항상 정렬되어 있어야한다. (오름차순, 내림차순 무관)
2. lt 왼쪽 시작과 rt 배열의 마지막부분 0부터 시작이니 1을 빼준다.
3. while 문을 통해 lt가 rt보다 클 동안 동작시킨다. 당연한말..
4. mid를 lt와 rt를 더 한 값 /2 하고 소수점을 떼준다.
5. 원하는 타겟 넘버를 찾으면 braek; 해준다.
6. 그게 아니라 반으로 나눈 값이 20이고 찾는 타겟이 10이면
더 앞으로 가야 하기 때문에 rt를 mid-1 해주고,
찾는게 30이면 lt를 mid+1 해주면 된다.
Author And Source
이 문제에 관하여(JS 알고리즘 노트 (이진탐색)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jaeilnet/JS-알고리즘-노트-이진탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)