[알고리즘] 04. 이분 탐색(Binary Search)

<본 포스팅은 개인 공부 목적으로 작성되었습니다.>

✅ 이분 탐색(Binary Search)

이진 탐색이라고도 불리며 이미 정렬된 데이터에서 특정 값을 찾을 때 절반 씩 나눠가며 찾는 알고리즘이다.

• 분할 정복 알고리즘 (Divide and Conquer)
  • Divide(분할) : 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer(정복) : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고 아니면 또 나눈다.
• 이분 탐색(Binary Search)
  • Divide(분할) : 정렬된 데이터를 절반으로 나눈다.
  • Conquer(정복)
    • 검색할 값(Search) > 중간값이면 오른쪽에서 다시 데이터를 찾는다.
    • 검색할 값(Search) < 중간값이면 왼쪽에서 다시 데이터를 찾는다.

출처 - https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

순차 탐색과 비교를 하면 이분 탐색은 절반씩 나눠가며 탐색을 하기 때문에 순차 탐색보다 훨씬 빠르다는 것을 알 수 있다.

✔ 이분 탐색 구현

1. 이분 탐색을 하기 위해서는 일단 정렬된 데이터여야만 한다.
2. 정렬된 데이터중 가장 작은 값을 left, 큰 값을 right, middle값을 left와 right의 중간값으로 설정한다.
3. 탐색하고자 하는 데이터를 k라 한다면 k와 middle값을 비교한다.
   1. k > middle일 경우 데이터는 오른쪽에 있다는 뜻이므로 left값을 middle + 1로 바꾼다.
   2. k < middle일 경우 데이터는 왼쪽에 있다는 뜻이므로 right값을 middle - 1로 바꾼다.
   3. 새롭게 설정된 left와 right로 middle값도 다시 설정 후 1 - 3을 반복한다.

✔ 코드

#include <iostream>

using namespace std;

int main(void) {

    int arr[] = { 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 };

    int target = 37;
    int left = 0;
    int right = 16;
    int mid;
    bool flag = true;

    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] == target) {
            flag = false;
            break;
        }
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    if (flag) cout << -1;
    else cout << mid + 1;
}

위에 그림을 코드로 구현해 보았다. target, left, right, mid값을 설정하고 값이 없을 경우를 위해 flag도 선언해 주었다. while문을 돌면서 mid의 값과 target을 비교해 주었고 만약 같다면 flag를 false로 바꾸고 break 해 주었다. 값이 없다면 -1 있다면 mid는 0부터 시작했으므로 mid + 1을 출력해주었다.

✔ 결과

12

✔ 시간 복잡도

• O(log N)

참고자료

https://github.com/Yunhyunjo/Ready-For-Tech-Interview/blob/master/Algorithm/%EC%9D%B4%EB%B6%84%20%ED%83%90%EC%83%89(Binary%20Search).md