Javascript # 알고리즘 [binary search]

오늘은 이진탐색 알고리즘을 이용한 알고리즘 문제를 풀어봤다.

문제

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

입출력 예시

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1

먼저 이진탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간값을 기준으로 잡고 이 중간값과 찾고자 하는 n이라는 값을 비교한다. n이 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을 대상으로 다시 비교하고, n이 중간값보다 크면 중간값을 기준으로 우측의 데이터들을 대상으로 다시 비교를 해나가는 알고리즘이다.

코드는 아래와 같이 작성 할 수 있다.

const binarySearch = function (arr, target) { 
  let start = 0;
  let end = arr.length - 1;
  let mid = 0;

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

  return - 1;
};

arr에 [0, 1, 2, 3, 4, 5, 6]이라는 값이 있고 target이 2라고 가정하고 코드에 대입해보자
우선 중간값을 구하기위해 3가지 변수를 선언하였다. while문을 사용해서 start가 end보다 작거나 같을때까지 반복적으로 중간값과 비교하는 방식으로 작성하였다.
만약 target과 중간값이 같으면 그대로 중간값의 인덱스를 반환하고, 중간값이 target보다 클 경우 end에 mid - 1을 해줌으로써 기존 중간값에서 한칸 더 작은 값으로 end가 바뀌게된다. 그리고 다시 비교를 시작한다. 중간값이 target보다 작으면 start에 mid + 1을 해줌으로써 마찬가지로 중간값에서 한칸 더 큰 값으로 start를 바꿔준다. 그러면 기존 중간값보다 큰 수들 중에서만 비교를 하면 되는 방식으로 문제를 해결 할 수 있다.