이진 검색

선형 검색은 자료를 처음부터 끝까지 순회하며 검색하기 때문에 자료가 클수록 나쁜 효율을 보여줍니다. 그래서 이 단점을 보완하고자 등장한 방식이 이진 검색입니다.

---

1. 이진 검색

이진 검색(Binary Search)은 일반적으로 선형 검색보다 더 빠른 검색 속도를 보여주는 알고리즘입니다. 단 한가지 전제 조건이 있다면, 이진 검색은 정렬된 컬렉션에 대해서만 검색이 가능하다는 점 입니다. 그래서 정렬 방식에 따라 선형 검색보다 오래걸릴 수도 있습니다.

다음과 같은 배열에서 이진검색을 통해서 26을 검색해보겠습니다.

 

우선 배열 인덱스의 중앙에 있는 값을 검사합니다. 이 값이 우리가 찾는 키 값 26과 일치하는지 확인합니다. 만약 키 값보다 작다면 배열의 앞 부분을, 키 값보다 크다면 배열의 뒷 부분을 생각하지 않고 나머지 부분에 대해서만 검색을 시도합니다. 왜냐하면 이미 정렬되어있는 배열이기 때문에 더 작거나 큰 부분은 볼 필요가 전혀 없기 때문입니다.

 

나머지 부분에 대해 다시 한 번 중앙 값을 설정하고 그 값과 비교합니다. 마찬가지로 일치하면 검색에 성공한 것이고 일치하지 않았다면 필요없는 부분을 잘라냅니다.

 

예시에서는 두 번만에 찾았지만 계속 진행한다면 마지막 1칸으로 나누었을 때도 찾지 못하면 검색 실패가 됩니다.

 

 

2. 이진 검색 구현

export const binarySearch = (arr, key) => {
    //검색 부분의 맨 처음 head
    let head = 0;
    //검색 부분의 맨 뒤 tail
    let tail = arr.length - 1;

    //head === tail일때도 못찾았다면 검색 실패
    while (head <= tail) {
        //부분 배열의 중간 값을 지정하는 center 변수
        let center = parseInt((head + tail) / 2);

        //키와 중간 값이 일치하면 검색 성공
        if (key === arr[center]) {
            return console.log("검색 성공");
        }
        //키가 중간값보다 적으면 범위를 앞쪽 절반으로
        else if (key < arr[center]) {
            tail = center - 1;
        }
        //키가 중간값보다 크면 범위를 뒤쪽 절반으로
        //else문으로 처리 가능
        else if (key > arr[center]) {
            head = center + 1;
        }
    }

    return console.log("검색 실패");
};

import {binarySearch} from './study-code/search/binary-search.js';

const arr = [3, 9, 11, 15, 16, 21, 22,  26, 29];

console.log("검색 키: 26");
binarySearch(arr, 26);

console.log("검색 키: 4");
binarySearch(arr, 4);

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/search/binary-search.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록