이진탐색

function binarySearch(arr, findValue) {
  let left = 0;
  let right = arr.length - 1;
  let mid = Math.floor((left + right) / 2);

  while (left <= right) {
    console.log(left, '/', mid, '/', right);

    if (arr[mid] === findValue) {
      return mid;
    }

    if (arr[mid] < findValue) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }

    mid = Math.floor((left + right) / 2);
  }

  return -1;
}

const array = [1, 1, 5, 124, 400, 599, 1004, 2876, 8712];
console.log(binarySearch(array, 124));

=> 이진 탐색 알고리즘은 정렬되어있는 자료구조에서 요소를 찾을 때 logn 복잡도로 찾을 수 있는 알고리즘이다. 배열과 이진트리 방식으로 구현이 가능한데, 배열을 쓰도록 하자