이진탐색

완전탐색 중 단순 브루트포스는 모든 값을 읽어내기 때문에 가장 오래걸리지만 가장 확실한 방법입니다.

주어진 배열에서 어떤 값을 비교해서 최대 값을 찾거나 최소 값을 찾거나 이런 경우에는 배열을 2중으로 훑어야 하기 때문에

시간 복잡도는 O(n^2) 이 됩니다.

 

이진탐색 나무위키 그림입니다.

기본개념은 분할정복인데,

이유는 계속 반으로 나누면서(분할) 내가 원하는 조건에 상회하는지 지속적으로 살피는 것이기 때문이다.

이진탐색의 시간복잡도는 O(log N)으로 선형탐색 O(N) 보다 더 빠릅니다.

이유는 정말 간단하게도 분할을 하기 때문입니다.

 

이진탐색의 예시 코드 입니다.

left 또는 statrt 라고 표현하며 시작 지점과,

rigth 또는 End 라고 표현하는 끝 지점을 지정해주고

 

middle 지점은 left 와 rigth 를 더 한 값의 /2 를 해준 중간 지점을 찾게 해줍니다.

 

배열의 Middle 지점이 제가 원하는 값의 크기에 따라 좌우로 움직이며 계속 제가 제시한 값의 위치, 인덱스를 찾아서 반환해줄 것입니다.

function binarySearch(arr, elem) {
    let start = 0;
    let end = arr.length - 1;
    let middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2

console.log(
  binarySearch(
    [
      5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98,
      99,
    ],
    10
  )
); // 2
console.log(
  binarySearch(
    [
      5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98,
      99,
    ],
    95
  )
); // 16
console.log(
  binarySearch(
    [
      5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98,
      99,
    ],
    100
  )
); // -1)