Binary Search

Rank It

You have been given an array A consisting of N integers. All the elements in this array A are unique. You have to answer some queries based on the elements of this array. Each query will consist of a single integer x. You need to print the rank based position of this element in this array considering that the array is 1 indexed. The rank based position of an element in an array is its position in the array when the array has been sorted in ascending order.

Note: It is guaranteed that all the elements in this array are unique and for each x belonging to a query, value x shall exist in the array

Input Format

The first line consists of a single integer N denoting the size of array A. The next line contains N unique integers, denoting the content of array A. The next line contains a single integer q denoting the number of queries. Each of the next q lines contains a single integer x denoting the element whose rank based position needs to be printed.

Output Format

You need to print q integers denoting the answer to each query.

C++

#include <iostream>

#include <bits/stdc++.h>

using namespace std;
int binarySearch(int A[], int low, int high, int x) {
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (A[mid] < x)
            low = mid + 1;
        else if (A[mid] > x)
            high = mid - 1;
        else if (A[mid] == x)
            break;
    }
    return mid;
}
int main() {
    int size;
    cin >> size;
    int A[size];
    for (int i = 0; i < size; i++) {
        cin >> A[i];
    }
    sort(A, A + size);
    int q;
    cin >> q;
    while (q--) {
        int x, rank;
        cin >> x;
        rank = binarySearch(A, 0, size - 1, x);
        cout << rank + 1 << endl;
    }
    return 0;
}