[알고리즘, 자료구조] 이진탐색이란?

이진 탐색 (Binary serch)

이진탐색은 정렬된 리스트에서 검색범위를 반씩 줄여 나가면서 검색값을 찾는 알고리즘이다.

이진탐색은 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색범위가 절반씩 줄어들기 때문에 속도가 빠르다는 장점이 있다.

 

이진탐색을 사용하면 logn번만에 답을 찾는다. 이것은 빅오표기법으로 O(log n)이라 표기하고 로그시간 이라고 부른다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jkssleeky&logNo=220715543451

탐색방법 : 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지 알아내어 탐색의 범위를 반으로 줄인다.

 

 자바스크립트로 이진탐색 구현

const binarySearch = (target, data) => {
  let low = 0;
  let high = data - 1;
  let arry = [];
  let count = 0;
  for (let i = 0; i < data; i++) {
    arry.push(i);
  }

  while (low <= high) {
    count++;
    console.log(count + "번 탐색");
    let mid = Math.floor((low + high) / 2);
    if (target === arry[mid]) {
      return mid;
    } else if (target > arry[mid]) {
      low = mid + 1;
    } else if (target < arry[mid]) {
      high = mid - 1;
    }
  }
  return count;
};

binarySearch(89432, 1000000); //18번 탐색
binarySearch(1000000, 1000000); //20번 탐색

먼저 정렬된 배열을 만들기 위해 for문을 통해 0부터 원하는 숫자 data까지 포함되어있는 배열을 만들었다.

while문을 통해 횟수를 1씩 증가시켰고, (low+high)/2로 중간값을 찾고 해당 중간값이 타겟과 같은지, 큰지, 작은지를 판별하여 같을때 중간값을 반환하도록 하였다.

총 100만개의 배열에서 89432라는 임의의 값을 찾는데는 18번, 100만의 데이터를 찾는데는 20번 탐색하였다.

만약 순차적 탐색을 통해 100만을 찾았더라면 탐색을 100만회 진행하였을 것이다.