Grade 9 · Sorting and searchingCitește în română

First position with a value greater than or equal to x

Original: Prima poziție cu valoare mai mare sau egală cu x

O(log n)C++1757 lines2 examples

The idea

The binary search variant that does not stop at the first match: in an array sorted in increasing order, we look for the smallest position p with v[p] >= x. If v[mij] >= x, mij is a candidate (we keep it and search further left); otherwise the answer is to the right. If all values are smaller than x, the answer is n + 1.

Original description (Romanian)

Varianta de căutare binară care nu se oprește la prima potrivire: într-un vector sortat crescător, căutăm cea mai mică poziție p cu v[p] >= x. Dacă v[mij] >= x, mij este un candidat (îl reținem și căutăm mai la stânga); altfel răspunsul este în dreapta. Dacă toate valorile sunt mai mici decât x, răspunsul este n + 1.

Complexity
O(log n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

6
1 3 3 5 8 13
4

Expected output

4
Example 2

Input

6
1 3 3 5 8 13
3

Expected output

2

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

prima-pozitie-mai-mare-sau-egala.cpp
/*
 * Titlu: Prima poziție cu valoare mai mare sau egală cu x
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Varianta de căutare binară care nu se oprește la prima potrivire:
 *            într-un vector sortat crescător, căutăm cea mai mică poziție p cu
 *            v[p] >= x. Dacă v[mij] >= x, mij este un candidat (îl reținem și
 *            căutăm mai la stânga); altfel răspunsul este în dreapta. Dacă toate
 *            valorile sunt mai mici decât x, răspunsul este n + 1.
 * Complexitate: O(log n)
 *
 * Exemplu
 * Intrare:
 * 6
 * 1 3 3 5 8 13
 * 4
 * Ieșire: 4
 *
 * Exemplu
 * Intrare:
 * 6
 * 1 3 3 5 8 13
 * 3
 * Ieșire: 2
 */
#include <iostream>
using namespace std;

int v[100001];

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    cin >> x;
    int st = 1, dr = n, rez = n + 1;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (v[mij] >= x)
        {
            rez = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    cout << rez << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.