binary search(이분검색)

풀이 binary search(이분검색)
binary search는 항상 정렬이 되어있을때만 사용가능하다.
정렬이 되어있지 않을경우 sort메소드를 사용하게되는데
sort메소드는 On(logn)이므로
binary search의 O(logn)과 합쳐져서
On(logn)만큼의 시간이 걸리게된다. 그러므로 이분검색은 정렬이 되어있을때 큰 성능 효과를 이룰 수있다.

// 결론 - 배열이 정렬되어있을때는 binary search(이분검색)를 사용하자.
// 이분검색() -> 정렬 On(logn) + O(logn) = On(logn)
function solution(target, arr) {
  let answer = 0;
  let count = 0; // 몇번
  let lt = 0;
  let rt = arr.length - 1;

  arr.sort((a, b) => a - b);

  while (lt <= rt) {
    count++;
    let mid = parseInt((lt + rt) / 2, 10);
    if (arr[mid] === target) {
      console.log('count = ', count);
      answer = mid + 1;
      break;
    } else if (arr[mid] > target) {
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }
  return answer;
}

console.log(solution(32, [23, 87, 65, 12, 57, 32, 99, 81]));
console.log(solution(70, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]));

풀이 indexOf 방식

// // indexOf -> 정렬 On(logn) + ON(logn) = On(logn)
function solutions(target, arr) {
  arr.sort((a, b) => a - b);
  const targetIndex = arr.indexOf(target);
  return targetIndex + 1;
}

console.log(solutions(32, [23, 87, 65, 12, 57, 32, 99, 81]));
console.log(solutions(70, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]));