Why is C # Array.BinarySearch so fast?

Question

I just implemented a very simple binarySearch algorithm in C # to find integers in an integer array:

Binary search

static int binarySearch(int[] arr, int i) { int low = 0, high = arr.Length - 1, mid; while (low <= high) { mid = (low+high)/2; if (i < arr[mid]) high = mid-1; else if (i > arr[mid]) low = mid+1; else return mid; } return -1; } 

When comparing with C # native Array.BinarySearch() I can see that Array.BinarySearch() is twice as fast as my function, every time.

MSDN on Array.BinarySearch :

Searches for the entire one-dimensional sorted array for a specific element using the universal IComparable interface implemented by each element of the array and the specified object.

What makes this approach so fast?

Test code

 using System; using System.Diagnostics; class Program { static void Main() { Random rnd = new Random(); Stopwatch sw = new Stopwatch(); const int ELEMENTS = 10000000; int temp; int[] arr = new int[ELEMENTS]; for (int i = 0; i < ELEMENTS; i++) arr[i] = rnd.Next(int.MinValue,int.MaxValue); Array.Sort(arr); //Custom binarySearch sw.Restart(); for (int i = 0; i < ELEMENTS; i++) temp = binarySearch(arr, i); sw.Stop(); Console.WriteLine($"Elapsed time for custom binarySearch: {sw.ElapsedMilliseconds}ms"); //C# Array.BinarySearch sw.Restart(); for (int i = 0; i < ELEMENTS; i++) temp = Array.BinarySearch(arr,i); sw.Stop(); Console.WriteLine($"Elapsed time for C# BinarySearch: {sw.ElapsedMilliseconds}ms"); } static int binarySearch(int[] arr, int i) { int low = 0, high = arr.Length - 1, mid; while (low <= high) { mid = (low+high)/2; if (i < arr[mid]) high = mid-1; else if (i > arr[mid]) low = mid+1; else return mid; } return -1; } } 

Test results

 +------------+--------------+--------------------+ | Attempt No | binarySearch | Array.BinarySearch | +------------+--------------+--------------------+ | 1 | 2700ms | 1099ms | | 2 | 2696ms | 1083ms | | 3 | 2675ms | 1077ms | | 4 | 2690ms | 1093ms | | 5 | 2700ms | 1086ms | +------------+--------------+--------------------+ 

Answer 1

Your code runs faster if you run Visual Studio:

Your vs array:

 From VS - Debug mode: 3248 vs 1113 From VS - Release mode: 2932 vs 1100 Running exe - Debug mode: 3152 vs 1104 Running exe - Release mode: 559 vs 1104 

Array code can already be optimized within the framework of the framework, but it also performs a larger check than your version (for example, your version can overflow if arr.Length larger than int.MaxValue / 2 ) and, as already mentioned, is intended for a wide range types, not just int[] .

So basically, it is slower only when debugging your code, because Array code always runs in release and with less control behind the scenes.