Binary Search

정의

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘

중간의 값을 임의로 선택하고 비교

해당 값을 찾을 때까지 이 과정을 반복

복잡도

시간복잡도

𝑂(log𝑛)

과정

탐색의 종료 조건은 원하는 값을 찾으면 종료

탐색하고자 하는 배열이 더이상 존재하지 않으면 찾고자 하는 값이 배열에 존재하지 않는것

탐색 종료

구현

기본


private static int binarySearch(int target) {
    // 정렬
    Arrays.sort(arr);

    int l = 0;
    int r = arr.length - 1;

    while (l < r) {
        int mid = (l + r) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        else if (arr[mid] < target) {
            l = mid + 1;
        }
        else if (arr[mid] > target) {
            r = mid - 1;
        }
    }

    // 값이 없으면 음수로 넣을 위치를 알려줌
    return -1 * l;
}

중복되는 값이 있으면 맨 뒤의 값


private static int upperBound(int target) {
    // 정렬
    Arrays.sort(arr);

    int l = 0;
    int r = arr.length;

    while (l < r) {
        int mid = (l + r) / 2;

        if (arr[mid] <= target) {
            l = mid + 1;
        }
        else if (arr[mid] > target) {
            r = mid;
        }
    }

		// 넣어야 할 위치를 return
    return l;
}

중복되는 값이 있으면 맨 앞의 값


private static int lowerBound(int target) {
        // 정렬
        Arrays.sort(arr);

        int l = 0;
        int r = arr.length;

        while (l < r) {
            int mid = (l + r) / 2;

            if (arr[mid] >= target) {
                r = mid;
            }
            else if (arr[mid] < target) {
                l = mid + 1;
            }
        }

        // 넣어야 할 위치를 return
        return l;
    }

문제

수 찾기


//1920-수 찾기-Silver4-https://www.acmicpc.net/problem/1920

#include <iostream>
#include <algorithm>

#define fastIo cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)

using namespace std;

int N, M;
int arr[100001];
int input;

int binarySearch(int target, int start, int end) {
    int idx = start + (end - start) / 2;
    int value = arr[idx];

    if (target == value) {
        return 1;
    }

    if (end - start > 1) {
        if (target < value) {
            return binarySearch(target, start, idx);
        } else {
            return binarySearch(target, idx, end);
        }
    } else {
        return 0;
    }
}

int main() {
    fastIo;

    //입력
    cin >> N;

    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    //정렬
    sort(arr, arr + N);

    cin >> M;

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

        cout << binarySearch(input, 0, N);

        if (i < M - 1) {
            cout << '\n';
        }
    }
}

정수 제곱근


//2417-정수 제곱근-Silver4-https://www.acmicpc.net/problem/2417

#include <iostream>

#define fastIo cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)

using ull = unsigned long long;
using namespace std;

ull input;

ull squareRoot(ull n) {
    ull min = 0;
    ull max = 3037000500;
    ull guess;
    ull value;

    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        while (min <= max) {
            guess = (min + max) / 2;
            value = guess * guess;

            if (value == n)
                return guess;
            else if (value > n) {
                if ((guess - 1) * (guess - 1) < n) {
                    return guess;
                }
                max = guess - 1;
            } else {
                if ((guess + 1) * (guess + 1) > n) {
                    return guess + 1;
                }
                min = guess + 1;
            }
        }
    }
}

int main() {
    fastIo;

    //입력
    cin >> input;

    cout << squareRoot(input);
}

예시

Binary Search Tree