이진 탐색(Binary Search)

이진 탐색(binary search)알고리즘은 정렬되어있는 데이터에서 특정 값의 위치를 찾는 알고리즘이다.

 

※정렬되어있지 않은 데이터에 사용할 수 없다※

 

재귀로 구현하면 매우 간단해진다.

 

• 중간 값(mid)을 잡는다
• 원하는 값을 찾지 못하였을 때 탈출 조건(first > last)에 의해 -1을 반환한다 : 탐색 실패
• 원하는 값을 찾았을 때(arr[mid] == key) 해당 위치(mid)를 반환한다 : 탐색 성공
• 현재 중간 값이 찾고자 하는 값보다 큰 경우, 중간 값의 왼쪽 범위에서 탐색을 시작한다 : 재귀 호출
• 현재 중간 값이 찾고자 하는 값보다 작은 경우, 중간 값의 오른쪽 범위에서 탐색을 시작한다 : 재귀 호출

---

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int binary_search(int arr[], int first, int last, int key)
{
    int mid = (first + last) / 2;
    if(first > last) return -1;
    if(arr[mid] == key) return mid;
    else if(arr[mid] > key) return binary_search(arr, first, mid - 1, key);
    else return binary_search(arr, mid + 1, last, key);
}

int main()
{
    int n;
    cin>>n;
    int* arr = new int[n];
    for(int i = 0 ; i < n ; i++) cin>>arr[i];

    sort(arr, arr+n);

    int quest;
    while(1)
    {
        cin>>quest;
        if(quest == -1) break;
        if(binary_search(arr, 0, n-1, quest) != -1) cout<<"find "<<quest<<endl;
        else cout<<quest<<" not found"<<endl;
    }

    return 0;
}