[알고리즘] 이진 탐색

✅ 이진 탐색 (Binary Search)

❕ 기본 개념 

- 배열에서 데이터를 탐색하는 알고리즘

- 선형 탐색과 달리, 데이터가 정렬된 경우에만 적용할 수 있음

- 배열의 가운데에 있는 데이터와 대상 데이터를 비교해서 대상 데이터가 정중앙보다 오른쪽에 있는지, 왼쪽에 있는지 확인

- 비교 작업을 대상 데이터를 찾거나 존재하지 않는다는 것을 확인할 때까지 반복

- 탐색 범위를 매번 반씩 줄여나갈 수 있는 탐색 알고리즘

- n개의 데이터를 반으로 나누는 작업을 log₂n회 반복 = 계산 시간은 O(log n)

 

 

❕ 작동 방식 

 

 

 

 

✔ 구현 방법 (JS) 

function binarySearch(sortedArray, key) {
  let start = 0;
  let end = sortedArray.length - 1;

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

    if (sortedArray[middle] === key) {
      // found the key
      return middle;
    } else if (sortedArray[middle] < key) {
      // continue searching to the right
      start = middle + 1;
    } else {
      // search searching to the left
      end = middle - 1;
    }
  }
  // key wasn't found
  return -1;
}

 

 

참고자료

「알고리즘 도감」 中 3-2 이진 탐색

https://stackabuse.com/binary-search-in-javascript/

https://github.com/charliegerard/dev-notes/blob/master/dataStructuresAlgorithms/binarySearch.md