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

1. 이진 탐색(Binary Search)

시간 복잡도 : O(logN)

데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다.
정렬된 리스트에서의 중앙값과 찾고자 하는 값을 비교하고, 리스트의 크기를 절반씩 줄이면서 대상을 찾는다.

gif script)

1) 5라는 값을 찾는 경우, 0~9 리스트에서 mid인 4와 5를 비교한다.
2) 4는 5보다 작으므로, 4의 뒤에 있는 리스트의 mid인 7과 5를 비교한다.
3) 7은 5보다 크므로, 4의 뒤, 7의 앞을 리스트로 두고 해당 리스트의 mid인 5와 5를 비교한다.
4) 5를 찾아 탐색이 완료되었다.

ex) 이진 탐색 예제(백준 1920)_(while-for문)

gif script대로 binarySearch를 생성하고 사용한다. vector를 binarySearch에 넘겨줄 때, a를 전역으로 두고 이용해도 된다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int N, M;

void binarySearch(int val, vector<int> &a) {
    int start = 0;
    int end = N - 1;
    while(start<=end){
        int mid = (start + end) / 2;
        if (val < a[mid]) {
            end = mid - 1;
        }
        else if (val > a[mid]) {
            start = mid + 1;
        }
        else {
            cout << 1 << "\n";
            return;
        }
    }
    cout << 0 << "\n";
    return;
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    vector<int> a(N);

    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    cin >> M;
    for (int i = 0; i < M; i++) {
        int val;
        cin >> val;
        binarySearch(val, a);
    }
    return 0;
    

}

ex) 이진 탐색 예제(백준 1920)_(재귀)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int N, M;

void binarySearch(int s, int e, int val, vector<int> &a) {
    //int start = 0;
    //int end = N - 1;
  if (s > e) {
    cout << 0 << "\n";
    return;
 }
 int mid = (s + e) / 2;
 if (val == a[mid]) {
 	cout << 1 << "\n";
     return;
 }else if (val > a[mid]) {
 	s = mid + 1;
    binarySearch(s, e, val, a);
 }else if(val<a[mid]){
 	e = mid - 1;
    binarySearch(s, e, val, a);
 }
 return;
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    vector<int> a(N);

    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    cin >> M;
    for (int i = 0; i < M; i++) {
        int val;
        cin >> val;

        //val을 발견하면 1을, 못하면 0을 출력하도록 한다.
        binarySearch(0, N-1, val, a);
    }
    return 0;
    

}

---

+) Binary Search gif(stackoverflow)