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

 

 

 

정렬이 보장되는 배열에서 기존 x를 가지고 범위를 ‘이분’하면서 탐색하는 방법

처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지닌다.

 

전체 탐색 → O(n)

이분 탐색 → O(logN)

 

 

🍒 오름차순 정렬된 배열의 특성

 

1. 임의의 m번 인덱스에 있는 A [m]이 x보다 크면, A[m...n]은 전부 x보다 크다.
2. 임의의 m번 인덱스에 있는 A [m]이 x보다 작으면, A[1...m]은 전부 x보다 작다.

 

L : 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스

R : 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스

result : 탐색한 x의 위치

탐색 목표: x 이하의 원소 중에 가장 오른쪽에 있는 원소

m = (L + R) / 2

 

→ x와 A[m] 비교!

 

 

🍒 과정

 

1. 정렬(필수)
2. left와 right로 mid 값 설정
3. mid와 구하는 값(x)과 비교
4. 구할 값이 mid보다 높으면 left = mid+1 구할 값이 mid보다 낮으면 right = mid - 1
5. left > right 될 때까지 반복

 

🍒 코드(c++)

//반복문
bool BinarySearch(int arr[], int l, int r, int key){
    while(l <= r){
        int mid = (l+r)/2;
        if(arr[mid] == key) return true;
        else if(arr[mid] > key) r = mid - 1;
        else l = mid + 1;
    }
    return false; //key가 없는 경우
}

//재귀함수
bool BinarySearch(int arr[], int l, int r, int key){
    if(l>r) return false;
    int mid = (l+r)/2;

    if(arr[mid] == key)     return true;
    else if(arr[mid] > key) return BinarySearch(arr, l, mid - 1, key);
    else                    return BinarySearch(arr, mid+1, r, key);
}

int main(){
    int n = 100;
    int arr[n];
    for(int i=0; i<n; i++) arr[i] = i; //sort 안 되어있으면 해야됨
    BinarySearch(arr, 0, n-1, 720) ? cout << "exist\\n" : cout << "not exist\\n" ;
}

 

//c++ STL에서 binary_search 사용 가능
#include<iostream>
#include<algorithm>
using namespace std;
 
//STL를 이용한 이진탐색을 이용하여 탐색
int main(){
    int n= 100;
    int arr[n];
 
    for(int i=0; i<n; i++){
        arr[i] = i;
    }

    binary_search(arr, arr+n, 70) ? cout << "exist\\n" : cout << "not exist\\n" ;
    
    return 0;
}

 

🍒 시간 복잡도

 

A[m]과 x를 한 번 비교할 때마다 [L, R] 구간이 절반씩 좁아진다.

구간의 길이 = N → N/2 → N/4 →... → 1 순서로 구간이 점점 좁아진다.

즉, ‘총 비교 횟수’ 는 ‘구간의 변화 횟수’인O(logN) 만에 원하는 값을 탐색한다.

→ 만약 N = 10 이면, log(10만) → 약 16

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!

 

 

 

 

 

참고: https://blockdmask.tistory.com/167