알고리즘 기초_ 이진탐색

이진탐색이란?

이진탐색은 입력으로는 정렬된 원소 리스트를 받음.
원하는 원소가 있으면 그 원소의 위치를 반환하고 아니면 null.

아래 코드로 설명

function binary_search(arr, key){
  let low = 0;
  let high = arr.length - 1;
  
    while (low <= high) {
      let mid = parseInt((low + high) / 2, 10);
      let guess = arr[mid];
      
      if (guess === key) {
          return mid;
        } else if (guess > key) {
          high = mid - 1;
        } else if (guess < key) {
          low = mid + 1;
        }
      }
    return console.log("key가 arr에 없음");
}

let arr = [1, 3, 5, 7 ,9];

제일 작은 인덱스(low)와 제일 큰 인덱스(high)를 찾아 놓고 중간 인덱스(mid)를 찾음. 그리고 arr의 중간 인덱스 값과 key값을 비교해서 범위를 좁혀나감.

빅오는 log로 나타남.