Skip to content
Katabench
Try free

Batched Binary Search

Easy About 10 min Free, no account needed

Answer twenty thousand membership queries against a sorted array.

The brief

Given a sorted integer array nums and an array queries, return how many queries are present in nums.

The performance bar

The obvious approach scans the whole array for every query, O(q * n). The hidden test runs 20,000 queries against 200,000 elements, and half the queries are absent (a full scan each). The array is sorted, so each query should cost far less than a full scan; the whole batch needs to fall from billions of comparisons to a few hundred thousand.

Starter code

C#
using System;

public class Solution
{
    // TODO: return how many of the queries appear in the sorted array nums.
    public int CountFound(int[] nums, int[] queries)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Binary search
Halve a sorted search space, with exact boundaries and no off-by-one drift.

Related katas