Binary Search

[devLupin]

int binary_search(int target)
{
    int start = 0, end = N - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == target) return 1;
        else if (arr[mid] < target)  start = mid + 1;
        else end = mid - 1;
    }
    return 0;
}

[devLupin]

Lower Boundary, Upper Boundary

---

• Lower bound : target 이상의 값이 처음 나오는 위치
• Upper bound : target보다 큰 값이 처음 나오는 위치

• 이분탐색 시 같은 값이 몇 개 있는지 확인할 때 사용할 수 있다.
• ans = upper_bound - lower_bound
• 단, upper_bound가 arr_sz - 1인 경우는 ans 값을 한 개 올린 값으로 사용해야 한다.

Code

• a는 비교할 배열

int lower_bound(int target) {
    int s = 0, e = a.size() - 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (a[m] >= target) e = m;
        else s = m + 1;
    }
    return e;
}
int upper_bound(int target) {
    int s = 0, e = a.size() - 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (a[m] > target) e = m;
        else s = m + 1;
    }
    return e;
}

int main(void) 
{
    // 탐색을 원하는 숫자 입력받고,
    // upper - lower
    for (int tmp, i = 0; i < M; i++) {
        cin >> tmp;
        int lower = lower_bound(tmp);
        int upper = upper_bound(tmp);
        int ans = upper - lower;
        if (upper == N - 1 && a[N - 1] == tmp) ans++;    // exception

        cout << ans << ' ';
    }
    return 0;
}

[devLupin]

example

---

• N개의 수열에서 세 개의 수 합이 0이 되는 경우의 수

#include <bits/stdc++.h>
using namespace std;

int n, A[10005];
long long ans;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> A[i];

    sort(A, A+n);

    for(int i=0; i<n-2; i++) {
        for(int j=i+1; j<n-1; j++) {
            int cmp = A[i] + A[j];
            int l = lower_bound(A + j + 1, A + n, -cmp) - A;
            int u = upper_bound(A + j + 1, A + n, -cmp) - A;
            ans += u-l;
        }   
    }

    cout << ans;

    return 0;
}