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 해주면 된다.

좋은 웹페이지 즐겨찾기