using System;

using System.Collections.Generic;

using System.Diagnostics;

​

​

public class Program

{

    static int iterations;

    public static void Main()

    {

        int entityLen =  100000; // that is M

        int dataLen   = 1000000; // that is N

​

        List<long> entityList = new List<long>();

        for (int i=0; i<entityLen; ++i)

        {

            // sparse data test - 

            entityList.Add( i*(dataLen/entityLen) + (dataLen/entityLen)/2 );

​

            // very collapsed data test

            // entityList.Add(i*1+0);

        }

        long[] dataList = new long [dataLen];

        for (int i=0; i<dataLen; ++i)

        {

            dataList[i] = i;

        }

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();

        iterations = 0;

        // 1st method: find one-by-one

        int listCount = 0;      

        int foundIndex = 0;

        for(;;)

        {

            foundIndex = SearchIndex(entityList[listCount], ref dataList, foundIndex, dataLen-1);

            if (foundIndex == -1) break;

            // Console.WriteLine("method 1 => {0}", foundIndex);

            // letting this operation inside SearchIndex() is awful

            listCount++;

            if (listCount == entityList.Count) break;

​

        }

        stopWatch.Stop();

        long elapsed01 = stopWatch.ElapsedTicks;

​

        Console.WriteLine("instances found: {0}. Elapsed Time, 1st method: {1} ticks, {2} iterations", listCount, elapsed01, iterations);

        // 2nd method: 

        // every time you find a value, you limit the range to be searched by the returned index until all values are gone.

        List<long> results = new List<long>();

​

        stopWatch = new Stopwatch();

        stopWatch.Start();

        iterations = 0;

        SearchAndDivideRange(ref entityList, 0, entityList.Count-1, ref dataList, 0, dataLen-1, ref results);

​

        stopWatch.Stop();

        long elapsed02 = stopWatch.ElapsedTicks;

        foreach(long index in results)

        {

        //  Console.WriteLine("method 2 => {0}", index);            

        }

        Console.WriteLine("instances found: {0}. Elapsed Time, 2nd method: {1} ticks, {2} iterations", results.Count, elapsed02, iterations);

​

    }

    static private void SearchAndDivideRange(ref List<long> entityList, int eStart, int eEnd, ref long[] dataList, int dataStart, int dataEnd, ref List<long> results)

    {

        if (eEnd < eStart || dataEnd < dataStart) return;

        int eMid = eStart + (eEnd-eStart)/2;

​

        // search midEntiy in the given range.

        int midDataIndex = SearchIndex(entityList[eMid], ref dataList, dataStart, dataEnd);

        if (midDataIndex != -1)

        {

            results.Add(midDataIndex);

        }

        // search now in the left range of dataList the left range of entityList

        {

            int dataStartLeft = dataStart;

            int dataEndLeft = midDataIndex == -1 ? dataEnd : midDataIndex-1;

            int eStartLeft = eStart;

            int eEndLeft = eMid-1;

            SearchAndDivideRange(ref entityList, eStartLeft, eEndLeft, ref dataList, dataStartLeft, dataEndLeft, ref results);

        }

        // idem in the right range

        {

            int dataStartRight = midDataIndex == -1 ? dataStart : midDataIndex+1;

            int dataEndRight = dataEnd;

            int eStartRight = eMid+1;

            int eEndRight = eEnd;

            SearchAndDivideRange(ref entityList, eStartRight, eEndRight, ref dataList, dataStartRight, dataEndRight, ref results);

        }

    }

    static private int SearchIndex(long entity, ref long[] dataList, int dataStart, int dataEnd)

    {

            int mid;

​

            while (dataStart <= dataEnd)

            {

                iterations++;

                mid = (dataStart + dataEnd) / 2;

                long target = dataList[mid];

                if (target == entity)

                {

                    return mid;

                }

                else

                {

                    if (target < entity)

                    {

                        dataStart = mid + 1;

                    }

​

                    if (target > entity)

                    {

                        dataEnd = mid - 1;

                    }

                }

            }

            return -1; //if the element in the list is not in the dataset

    }

​

}