Modified Binary Search algorithm exceeding time limit

Question

You are given a sorted array of numbers, and followed by number of queries, for each query if the queried number is present in the array print its position, else print -1.

Input

First line contains N Q, number of elements in the array and number of queries to follow,

Second line contains N numbers, elements of the array, each number will be -10^9<= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5

Reference:https://www.spoj.com/problems/BSEARCH1/

My code works fine on terminal but it excedes the time limit on the online judge even though it takes O(NQ) time.

Here is my code:

#include <iostream>

long long binarySearch(long long arr[], long long l , long long r , long long x) {
    long long mid;
    if (r >= l){ 
        mid = (l+r)/2;
        if (arr[mid] == x) {
            if (arr[mid] == arr[mid-1]) {
                while (arr[mid] == arr[mid-1]) {
                    --mid;
                }
                return mid;
            }
            else{
                return mid;
            }
        } 
        if (arr[mid] > x) {
            return  binarySearch(arr,l,mid-1,x);
        } 
        if (arr[mid] < x) {
            return binarySearch(arr,mid+1,r,x);
        }
    }
    return -1;
}

int main() {
    long long n ,q;
    std::cin >> n >> q;
    long long array[n];
    for (long long i = 0; i < n; ++i) {
        std::cin >> array[i];
    }
    long long x;
    long long arr2[q];
    for (long long i = 0 ; i < q ; ++i) {
        std::cin >> x;
        std::cout << binarySearch(array,0,n-1,x) << "\n";

    }
    return 0;
}

Answer 1

You don't need to reinvent the wheel. You can use the C++ standard library algorithm std::lower_bound. It does a binary search for the first location where the value could be.

You can rewrite your function as follows:

#include <algorithm>

long long binarySearch(long long arr[], long long n, long long x)
{
    // O(log n) binary search for first element not less that x
    long long *itr = std::lower_bound(arr, arr + n, x);

    // If itr is array end or location doesn't contain x
    if (itr == arr + n || *itr != x) {
        return -1;
    }

    // Compute index by address arithmetic
    return itr - arr;
}

I've removed one unnecessary function parameter, just pass the array size. By the way, you don't need long long for this problem. Might as well use int and save some memory.

If you still have timeout problems it might be slow input/output. Try adding the next two lines at the beginning of your main().

std::ios_base::sync_with_stdio(false); // possibly faster I/O buffering
std::cin.tie(NULL); // don't flush output stream before doing input