Benchmark.cs

using System;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;

namespace BenchForFun
{
    public class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Tester>();
        }
    }

    [SimpleJob(targetCount: 5000)]
    public class Tester
    {
        readonly Random random = new Random();
        const int N1 = 3000;
        const int N2 = 10;

        int[] data;
        int[] keys;        

        private void RandomizeData()
        {
            var hs = new HashSet<int>();
            for (var i = 0; i < N1; i++)
            {
                while (!hs.Add(random.Next()));
            }
            System.Diagnostics.Debug.Assert(hs.Count == N1);
            data = hs.ToArray();
            Array.Sort(data);
        }

        private void RandomizeKeys()
        {
            var hs = new HashSet<int>();
            for (var i = 0; i < N2; i++)
            {
                while (!hs.Add(random.Next(N1)));
            }
            System.Diagnostics.Debug.Assert(hs.Count == N2);
            keys = hs.Select(x => data[x]).ToArray();
            Array.Sort(keys);
        }

        [IterationSetup]
        public void IterationSetup()
        {
            RandomizeData();
            RandomizeKeys();
        }

        [Benchmark]
        public int[] FindByLinear()
        {
            var result = new int[N2];
            int pos = 0;
            int count = 0;
            for (var i = 0; i < result.Length; i++)
            {
                var key = keys[i];
                for (; pos < data.Length; pos++)
                {
                    if (data[pos] == key)
                    {
                        result[i] = pos;
                        count++;
                        break;
                    }
                }
            }
            if (count == N2)
            {
                return result;
            }
            throw new Exception($"count = {count}, pos = {pos}");
        }

        [Benchmark]
        public int[] FindByNaiveBisearch()
        {
            var result = new int[N2];
            int count = 0;
            for (var i = 0; i < result.Length; i++)
            {
                var key = keys[i];
                var p = Array.BinarySearch<int>(data, 0, N1, key);
                if (p >= 0)
                {
                    result[i] = p;
                    count++;                    
                }
            }
            if (count == N2)
            {
                return result;
            }
            throw new Exception($"count = {count}");
        }

        [Benchmark]
        public int[] FindByBisearch()
        {
            var result = new int[N2];
            int pos = 0;
            int count = 0;
            for (var i = 0; i < result.Length; i++)
            {
                var key = keys[i];
                var p = Array.BinarySearch<int>(data, pos, N1 - pos, key);
                if (p >= 0)
                {
                    result[i] = p;
                    pos = p;
                    count++;                    
                }
            }
            if (count == N2)
            {
                return result;
            }
            throw new Exception($"count = {count}");
        }
    }
}

report.md

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.20251
Intel Core i5-3337U CPU 1.80GHz (Ivy Bridge), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.1.302
  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  Job-OHODCH : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT

InvocationCount=1  IterationCount=5000  UnrollFactor=1  

Method	Mean	Error	StdDev	Median
FindByLinear	10.364 μs	0.1725 μs	3.641 μs	9.400 μs
FindByNaiveBisearch	8.114 μs	0.1743 μs	3.710 μs	7.500 μs
FindByBisearch	8.102 μs	0.1748 μs	3.709 μs	7.300 μs