[탐색] 이분탐색 Binary Search

이분탐색 (Binary Search)

오름차순으로 정렬된 N개의 수열에서 탐색하는 알고리즘이다.

탐색을 진행할수록 수의 범위는 반으로 줄어든다.

시간복잡도는 O(logN)

이분탐색 순서는 다음과 같다.

1. 오름차순으로 정렬하기

2. left는 배열의 첫 인덱스(0), right는 배열의 마지막 인덱스(N-1), mid는 (left + right) / 2로 지정

3. mid와 찾고자하는 값(val) 비교

mid == val : 찾음!

mid < val : left = mid + 1 (수의 범위를 오른쪽으로 옮긴다고 생각하면됨!)

mid > val : right = mid - 1 (수의 범위를 왼쪽으로 옮긴다고 생각하면됨!)

4. left가 right보다 더 커지면 탐색 끝! (또는 찾으면 탐색 끝!)

구현예시코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[10], val;
 
void BS(int x) {
    int left, right, mid;
    left = 0;
    right = 9;
    while (left <= right) {
        mid = (left + right) / 2;
        if (a[mid] == x) {
            printf("있음!\n");
            return;
        }
        else if (a[mid] < x)
            left = mid + 1;
        else if (a[mid] > x)
            right = mid - 1;
    }
    printf("없음!ㅠㅠ\n");
    return;
}
 
int main(){
    for (int i = 0; i < 10; i++)
        scanf("%d", &a[i]);
    scanf("%d", &val);
 
    sort(a, a + 10);
    BS(val);
 
    return 0;
}

구현예시코드-결과

  

[STL] binary_search()을 이용하는 방법

c++에서 굳이 위에처럼 구현하지 않아도

algorithm 라이브러리에 있는 binary_search() 를 이용하면 쉽게 이분탐색할 수 있다.

binary_search(배열의처음, 배열의끝, 찾으려는 값)

있으면 true return, 없으면 false return

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main(){
    int a[10], val;
    for (int i = 0; i < 10; i++)
        scanf("%d", &a[i]);
    scanf("%d", &val);
 
    sort(a, a + 10);
 
    if(binary_search(a, a+10, val)) 
        printf("있음!\n");
    else
        printf("없음!ㅠㅠ\n");
 
    return 0;
}