# ITMO Academy Pilot Course - Binary Search

###### tags: `Steven` `Codeforces`

# [Step 1](https://codeforces.com/edu/course/2/lesson/6/1/practice)

## [A. Binary Search](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/A)

Implement a straight-forward binary search algorithm.

### Implement binary search

Using the normal approach.

#include <bits/stdc++.h>

using namespace std;

bool __binary_search(int inp[], int n, int target)
{
    int l = 0, r = n;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (inp[mid] == target)
            return true;
        else if (inp[mid] < target)
            l = mid;
        else
            r = mid;
    }

    return inp[l] == target; // this is a very crucial check
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);

        printf("%s\n", __binary_search(inp, n, num) ? "YES" : "NO");
    }

    return 0;
}

### Using lower bound

Since lower bound returns the first element that is not less than the target number, we can actually use it to check for the existence of the target!

#include <bits/stdc++.h>

using namespace std;

// returns the first element that is not less than target
// 10 10 20 20 20 30 40; target = 20
//       ^
//
// If all the elements in the range compare less than target, the function
// returns last
int __my_lower_bound(int inp[], int n, int target)
{
    int l = -1, r = n; // mind the left bound
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxvvvv
        //  lr
        if (target <= inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

bool __binary_search(int inp[], int n, int target)
{
    int l = 0, r = n;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (inp[mid] == target)
            return true;
        else if (inp[mid] < target)
            l = mid;
        else
            r = mid;
    }

    return inp[l] == target;
}

bool __binary_search_2(int inp[], int n, int target)
{
    int idx = __my_lower_bound(inp, n, target);
    return idx != n && inp[idx] == target;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);

        printf("%s\n", __binary_search_2(inp, n, num) ? "YES" : "NO");
    }

    return 0;
}

### Using `binary_search`

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);

        printf("%s\n", binary_search(inp, inp + n, num) ? "YES" : "NO");
    }

    return 0;
}

## [B. Closest to the Left](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/B)

For each query, print the maximum index of an array element not greater than the given one -> Find the lower bound of $target + 1$ or find the upper bound of $target$

(Index is 1-based)

### Lower bound

#include <bits/stdc++.h>

using namespace std;

// returns the first element that is not less than target
// 10 10 20 20 20 30 40; target = 20
//       ^
//
// If all the elements in the range compare less than target, the function
// returns last
int __my_lower_bound(int inp[], int n, int target)
{
    int l = -1, r = n; // mind the left bound
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxvvvv
        //  lr
        if (target <= inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);

        printf("%d\n", __my_lower_bound(inp, n, num + 1));
    }

    return 0;
}

### Upper bound

#include <bits/stdc++.h>

using namespace std;

// returns the first element that is not less than target
// 10 10 20 20 20 30 40; target = 20
//       ^
//
// If all the elements in the range compare less than target, the function
// returns last
int __my_lower_bound(int inp[], int n, int target)
{
    int l = -1, r = n; // mind the left bound
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxvvvv
        //  lr
        if (target <= inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

// returns the first element that is greater than target
// 10 10 20 20 20 30 40; target = 20
//                ^
//
// If none of the elements in the range compare greater than target, the
// function returns last
int __my_upper_bound(int inp[], int n, int target)
{
    int l = -1, r = n; // mind the left bound
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxxxvv
        //    lr
        if (target < inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);

        printf("%d\n", __my_upper_bound(inp, n, num));
    }

    return 0;
}

### Other solution

Using `l <= r`: [lucifer1004](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/submission/90660076)

## [C. Closest to the Right](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/C)

For each query, print the minimum index of an array element not less than the given one -> Find the lower bound of the target!

(Index is 1-based)

### Lower bound

#include <bits/stdc++.h>

using namespace std;

// returns the first element that is not less than target
// 10 10 20 20 20 30 40; target = 20
//       ^
//
// If all the elements in the range compare less than target, the function
// returns last
int __my_lower_bound(int inp[], int n, int target)
{
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxvvvv
        //  lr
        if (target <= inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);

        printf("%d\n", __my_lower_bound(inp, n, num) + 1);
    }

    return 0;
}

## [D. Fast search](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/D)

Given a sorted sequence `10 10 20 20 20 30 40`, how do you find the total amount of number `20` in $O(log(n))$ time?

The answer is `upper_bound(20) - lower_bound(20)`!

### Using the aforementioned concept

#include <bits/stdc++.h>

using namespace std;

// returns the first element that is not less than target
// 10 10 20 20 20 30 40; target = 20
//       ^
//
// If all the elements in the range compare less than target, the function
// returns last
int __my_lower_bound(int inp[], int n, int target)
{
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxvvvv
        //  lr
        if (target <= inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

// returns the first element that is greater than target
// 10 10 20 20 20 30 40; target = 20
//                ^
//
// If none of the elements in the range compare greater than target, the
// function returns last
int __my_upper_bound(int inp[], int n, int target)
{
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        // xxxxvv
        //    lr
        if (target < inp[mid])
            r = mid;
        else
            l = mid;
    }

    return r;
}

int main()
{
    int n;
    scanf("%d", &n);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);
    sort(inp, inp + n);

    int k;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int l, r;
        scanf("%d %d", &l, &r);

        // 1 3 4 10 10
        // [2, 10)
        printf("%d\n", __my_upper_bound(inp, n, r) - __my_lower_bound(inp, n, l));
    }

    return 0;
}

### Other solution

Using `l <= r`: [lucifer1004](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/submission/90660636)

# Step 2

# Step 3

# Step 4

# Step 5