[알고리즘] 이진탐색

최예닮·2022년 12월 30일

오늘은 이진탐색에 대해 알아보도록 하자

이진탐색이란 ?

정렬된 리스트에서 탐색 범위를 절반씩 줄여가며 값의 위치를 찾아내는 알고리즘이다
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.
시간복잡도는 탐색할 범위를 절반으로 줄여서 탐색하므로 O(logn)* 이다
O(logN) 이란? : 입력 크기(N)가 커질 때 연산 횟수가 logN 에 비례해서 증가하면 시간 복잡도는 O(logN)

과정을 정리를 해보자면

1) 데이터가 정렬되어 있어야 사용가능
2) 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘
3) 찾고자 하는 값이 X 라고 가정했을때
4) X 가 중간 값보다 작으면 중간값 기준으로 좌측 탐색
5) X 가 중간 값보다 크면 중간값 기준으로 우측 탐색
6) 그리고 이 방법으로 다시 중간의 값을 선택하여 X 값을 비교 하며 찾을때까지 이 과정을 반복

이해하기 쉽게 그림으로 한번 봐보자 🖼

따라서 순차적으로 배열을 비교하는 선형탐색(O(n))에 비해 이진탐색은 시간복잡도에서 크게 이점을 갖는다.

혹시 그림으로만 보면 이해가 덜 갈 수 있기 때문에 gif 파일 하나도 올려보겠다

어때요 ? 이해가 팍팍 되시쥬 ? ㅎㅎ steps 차이 보소 ...

이게 어떤 사람은 그렇게 말할 수 있다.

저기요 ? 🙋‍♂️ 만약에 숫자 3 을 찾는거면 선형탐색이 더 시간복잡도에서 이점이 있는게 아닌가요 ?

맞는 말이다. 하지만 데이터가 엄청 엄청 많으면 어쩔건데 ? 🤷‍♂️

만약에 40억개에 데이터를 찾으면 선형으로 검색시에 컴퓨터 터질듯

그런데 이진탐색을 사용하게 되면 최~~~대 32번 만에 찾을 수 있다. 크.. 외쳐 갓 이진탐색!!! 🥳

자 ! 이제 Javascript 로 한번 구현해보자

function binarySearch(array, targetValue) {
    let left = 0;
    let right = array.length - 1;
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        if(array[mid] === targetValue) {
            return array[mid];
        }
        else if(array[mid] > targetValue) {
            right = mid - 1;
        }
        else if(array[mid] < targetValue) {
            left = mid + 1;
        }
    }
    return notFound;
}

코드 설명

1)binarySearch 함수는 매개변수로 array 와 탐색을 원하는 숫자 targetValue 를 받는다.
2) 함수 내부에서 left와 right 를 각각 배열의 0번째, 마지막 인덱스로 초기화를 해준다.
3) while 문을 사용하여 left가 right 보다 작거나 같을 동안 탐색을 수행
4) while 문 안에서는 mid의 값을 구해주고 조건문을 통해 mid에 해당하는 인덱스의 요소가 탐색하고 있는 값과 같은지 비교

결과

5) 값이 같을 경우는 값을 반환하고 탐색 종료
6) mid 인덱스의 요소 > 탐색하는 값 → right의 값을 미드보다 1 작은 값으로 설정(right = mid - 1)
7) mid 인덱스의 요소 < 탐색하는 값 → left의 값을 미드보다 1 큰 값으로 설정(left = mid + 1)
8) while 문이 끝날 때까지 원하는 값을 찾지 못하면 while 문을 빠져나와 notFound 를 반환하고 탐색 종료