[알고리즘] 이분 탐색 (이진 탐색)

이 글은 혼자 공부하면서 적어간 내용이기에 평어체로 작성되었고 틀린 내용이 있을 수 있습니다.
이 점 양해부탁드리며 틀린 내용 지적, 질문은 언제든 환영합니다!

이분 탐색 (binary search)

이분 탐색(이진 탐색) 알고리즘은 정렬되어 있는 리스트에서 범위를 절반씩 좁혀가며 탐색해나가는 알고리즘이다.

• 이분 탐색은 탐색하고자 하는 데이터(ex 배열)가 반드시 정렬되어 있어야 한다.

탐색 과정

• start, end, mid 3개의 변수를 이용하여 탐색한다. start는 탐색하고자 하는 범위의 시작값, end는 범위의 마지막값, mid는 그 범위에서 중간값을 가리키고 있다.

• C++로 작성한 이분탐색 코드

int binary_search(int n, int target)
{
    int start = 0, end = n-1, ans=0;
    while(start<=end) {
        int mid = (start+end)/2;
        if(target < arr[mid]) end = mid-1;
        else if(target > arr[mid]) start = mid+1;
        else {
            ans = 1;
            break;
        }
    }
    return ans;
}

이분 탐색을 통해 찾는 값이 있다면 1을 반환하고, 없다면 0을 반환하는 코드이다.

1. 배열의 크기 n, 찾는 값 target을 받아와 배열의 처음과 끝의 index를 start와 end로 지정해준다.
2. mid에는 중간값 (정확히는 중앙의 index)을 넣어준다.
3. 찾는 값 target이 mid가 가리키는 값보다 작으면 end 값은 mid-1로 변경, 크다면 start 값을 mid+1로 변경한다.
4. start 혹은 end 값이 바뀌었으므로 mid값도 다시 변경하며 반복을 계속한다.
5. mid가 가리키는 값이 찾는 값과 일치하면 ans에 1을 저장하고 반복을 끝내며 혹은 end 값이 start 값 보다 작아지면 탐색을 종료한다.

예시

코드만 보아서는 이해가 조금 어려울 수 있으니 그림을 참고하여 보자.
위에서의 1,2번에 해당하는 과정이며 start = 0, end = 9, mid = (0+9)/2 -> 4의 값이 들어갔다. target = 4이다.
target이 arr[mid]보다 작으므로 end = mid-1 = 3이 되었고 mid = (0+3)/2 -> 1의 값이 들어갔다.
target이 mid보다 크므로 start = mid+1 = 2이 되었고 mid = (2+3)/2 -> 2가 되었다. arr[mid] = 4 = target이므로 탐색을 종료한다.

이분 탐색의 장점

• O(logN)의 시간 복잡도를 가지므로 매우 효율적이다.
  • 매 단계를 거치면서 탐색 범위를 반으로 줄여가므로 32 -> 16 -> 8 -> 4 -> 2 -> 1, 이런식으로 5단계를 거치고 밑이 2인 log의 결과와 같다.
  • 브루트포스 알고리즘을 사용한다면 처음부터 하나씩 다 탐색해보아야 하므로 O(N) -> 최대 32번을 탐색했어야 하지만 이분탐색으로 최대 5번안에 찾을 수 있다.

이분 탐색의 단점

• 정렬되어 있는 데이터에만 사용할 수 있다.
  - 정렬되어 있지 않은 데이터에는 정렬 시간이 추가로 소요될 수 있고, 이에 따라 사용하기 곤란한 상황이 있을 수 있다.

참고문헌

https://velog.io/@kimdukbae/이분-탐색-이진-탐색-Binary-Search
https://freedeveloper.tistory.com/275?category=888096