[JavaScript/section 7] 10 - 이분 검색

📌 10 - 이분 검색

임의의 N개의 숫자가 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수중 한 개의 수인 target이 주어지면 이분 검색으로 target이 정렬된 상태에서 몇 번째에 있는지 구하는 문제이다. 단, 중복값은 존재하지 않는다.

 

이분 검색 알고리즘이란❓

• 정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다.
• 이분 검색 알고리즘의 시간 복잡도는 O(logN)으로 순차 검색의 시간 복잡도 O(N)에 비하면 상대적으로 빠른 검색 알고리즘에 속한다. 다음 풀이 방법을 보면 그 이유를 알 수 있을 것이다.

 

풀이 방법

• 배열을 정렬한다. 이분 검색 알고리즘에서 가장 중요한 부분이다.
• 배열의 처음(start)과 끝(end)의 인덱스를 더한 후 2로 나누어 배열의 중간 인덱스(mid)을 구한다. 단, 인덱스는 소수점을 포함하지 않으므로 Math.floor() 함수를 이용해 소수점 이하를 반올림한다.
• 찾고자 하는 값(target)이 중간 값(arr[mid])보다 크면 중간 값을 포함한 하위 값들은 탐색 대상에서 제외된다.
• 반대로 찾고자 하는 값이 중간 값보다 작으면 중간 값을 포함한 상위 값들은 탐색 대상에서 제외된다.
• 찾고자 하는 값이 중간 값과 같다면 answer 변수에 중간 인덱스(mid) + 1을 저장하고 while 문을 빠져나온다. 

 

📝 풀이

function solution(target, arr) {
  let answer;
  arr.sort((a, b) => a - b);
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((end + start) / 2);

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

  return answer;
}

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

 

📚 참고한 사이트

https://kangworld.tistory.com/65

[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도