Something interesting about the Array’s BinarySearch in C#

Hello Friends, while solving one of the Longest Sub sequence problem in Hacker Rank I got to know about a very interesting property of binary search in arrays.  I will demo this feature of the array with examples and it can be very helpful while solving some algorithm problems.

What do you think is the output of the following code:

        public static void Main(string[] srgs)
        {
            int[] arr = {3, 5, 7, 8, 9, 10};
            int pos = Array.BinarySearch(arr, 6);
            Console.WriteLine(pos);            
        }

As you can see in the above code, I am trying to search a element 6 in the sorted array. But since the element is not present in the array. What the above code should return. Lets debug and see the result.

As you can see in the above screen shot, I am getting the value of pos as -3. But what is this value. Is this some arbitrary number. No it is not just any arbitrary number. It is the two’s complement of the position of the next bigger number in the array.

Well I was also not sure about this 2’s complement thing and all. And what exactly is 2’s complement and how should I get the position of next greater number out of this negative number.

There is an operator in C#. We usually call as Tilde(~) in keyboard. This operator converts the operands value to 2’s complement.

Lets see how it works in the code.

            int arrayPosition = ~pos;
            if(arrayPosition > arr.Length)
                Console.WriteLine("Reached tHe end");
            else
                Console.WriteLine("The next bigger element is: " + arr[arrayPosition]);

In the above code we get the position of the next bigger element i.e 7 in this case.

Top career enhancing courses you can't miss

My Learning Resource

Excel your system design interview