binary search

const arr = [1, 3, 5];
// const arr = [3];

// 타겟이 들어갈 인덱스 구하기
function solution(target) {
  if (arr.length === 0) return 0;
  function findIndex(i, j) {
    let m = Math.floor((i + j) / 2);

    if (i === j) {
      if (target < arr[m]) {
        // [...arr].splice(m, 0, target);
        return m;
      } else if (arr[m] < target) {
        // [...arr].splice(m + 1, 0, target);
        return m + 1;
      }
    }
    if (target < arr[m]) {
      return findIndex(i, m);
    } else if (target > arr[m]) {
      return findIndex(m + 1, j);
    }
  }
  return findIndex(0, arr.length - 1);
}

console.log(solution(0)); // 0
console.log(solution(2)); // 1
console.log(solution(4)); // 2
console.log(solution(8)); // 3