Wednesday, September 18, 2019

Binary Search algorithm with C# example:

In this blog, we will learn about the Binary search, it is the most popular search algorithm and more efficient and also it is most commonly used technique for search. Binary Search is also known as half-interval search, logarithmic search, or binary chop.

The Binary Search is an example of divide-and-conquer algorithm and it finds the position of a target value or key within sorted array. In binary search algorithm it compares the middle element of array to target value, if they are not equal, then half of elements in array will be eliminated and it continuous search on remaining half of array and again it will take the middle element to compare to target value and repeating until the target value is found.

Binary Search Implementation


Big O notation:

Binary Search is faster than linear search, it don’t compare to each n element of arrays, so in worst case, it makes O(logn) comparison

Here is a binary search algorithm implementation in C#

     static int BinarySearch(int[] arr, int low, int high, int key)
        {
           
            while(low <= high)
            {
                //Find middle position of array
                int m = (low + high) / 2;

                // Compare the middle element item to target value -key
                if(key == arr[m])
                {
                    return m;
                }
                else if (arr[m] > key)
                {
                    high = m-1;
                }
                else
                {
                    low = m+1;
                }
            }

            return -1;
        }


public static void Main()
        {
            #region binary search

            int[] arr = new int[] {  5, 6, 7, 10, 23 , 50 };

            foreach (var item in arr)
            {
                Console.Write(item.ToString() + ',');
            }

            Console.WriteLine();

            int key = 23;

            int index = BinarySearch(arr, 0, arr.Length - 1, key);

            Console.WriteLine($"Key : {key}  Position : {index}");

   #endregion

        Console.Read(); 
}


Console Output:

Binary Search algorithm  C#



No comments:

SQL Server - Identify unused indexes

 In this blog, we learn about the index usage information (SYS.DM_DB_INDEX_USAGE_STATS) and analyze the index usage data (USER_SEEKS, USER_S...