[JS Algorithm] 이진 탐색(Binary Search) 문제

이진 탐색이란?

- 데이터가 정렬된 배열에서 특정 값을 찾는 알고리즘

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방식

---

JS를 통한 이진 탐색 구현

배열 내에서 내가 찾아야 하는 target값이 주어졌을 경우, 해당 배열의 몇 번째에 내가 찾는 값이 있는지 찾아내보자

 

구현 순서

( 1 ) 배열을 정렬한다.

( 2 ) 시작 값(start)과 끝 값(end)을 설정한다.

( 3 )start가 end와 같아질 때까지 반복문을 돌린다.

( 4 ) 반복문 내에서, 시작 값과 끝 값의 중간 값(mid)을 정의한다.

( 5 ) 배열의  mid값과 target값을 비교한다.

       ( i ) mid < target일 경우, start = mid + 1을 해준다 -> mid 앞에 있는 값들은 필요하지 않기 때문 
       ( ii ) mid > target일 경우, end = mid - 1을 해준다 -> mid 뒤에 있는 값들은 필요하지 않기 때문

 

참고 이미지

---

---

function solution(target, arr) {
  arr.sort((a, b) => a - b);

  let start = 0;
  let mid;
  let end = arr.length - 1;

  while (start <= end) {
    mid = parseInt((start + end) / 2);

    if (arr[mid] === target) {
      return mid + 1;
    } else {
      if (arr[mid] < target) {
        start = mid + 1;
      }
      if (arr[mid] > target) {
        end = mid - 1;
      }
    }
  }
  return mid;
}

let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));