busca_binária

#include <bits/stdc++.h>
#define MAXN 50000
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

int v[MAXN];

/*
---Busca Binária---

A função a seguir retorna uma posição de x em v, se x não estiver contido retorna -1.

OBS: Não funciona para obter a primeira ocorrência de x.
*/

int busca_binaria(int v[], int n, int x){
    int l = 1;
    int r = n;

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

        if(v[mid] == x){
            return mid;
        }
        if(x > v[mid]){
            l = mid+1;
        }
        if(x < v[mid]){
            r = mid-1;
        }
    }

    return -1;
}

/*
A função binary_search(v, v+n, x) já está definida na STL e retorna true se x está contido em v ou false caso contrário.

---Lower Bound---

No vetor  v: lower_bound(v, v+n, x);
No vector v: lower_bound(v.begin(), v.end(), x);

Retorna o endereço de memória do primeiro valor >= x no vetor v. Se este valor não existir, retorna o endereço do fim do vetor.

---Upper Bound---

No vetor  v: upper_bound(v, v+n, x);
No vector v: upper_bound(v.begin(), v.end(), x);

Retorna o endereço de memória do primeiro valor > x no vetor v. Se este valor não existir, retorna o endereço do fim do vetor.

Lower e Upper devem só funcionam corretamente em um vetor ordenado.

Para contar o número de ocorrência de x da seguinte forma:

int freq = upper_bound(v, v+n, x) - lower_bound(v, v+n, x);
*/

int main(){

}