C# Coding Test Course, Binary Search

1. Problem Definition

Binary search is an algorithm for finding a specific value in a sorted array. It works by comparing the middle value of the array and halving the search range.
The time complexity of binary search is O(log n), making it very efficient. Let’s understand the principles of this algorithm by implementing it in practice.

2. Problem Description

The following problem involves finding a specific number using binary search:

        
            // Problem: Find a specific number in the given integer array.
            // The array is sorted in ascending order.
            // If the number is found, return its index, 
            // and return -1 if it is not found.
        
    

Example Input

• Input Array: [2, 3, 4, 10, 40]
• Value to Find: 10

Example Output

• Output: 3 (10 is located at index 3)

3. Problem Solving Strategy

The basic idea of binary search is as follows:

• Select the middle element of the array.
• Compare the middle element with the value to be found.
• If the value to be found is less than the middle element, reduce the search range to the left half of the array.
• If the value to be found is greater than the middle element, reduce the search range to the right half of the array.
• Repeat this process until the value to be found is found.

4. Algorithm Implementation

Now let’s implement the binary search algorithm in C#. The following code is an implementation of the binary search algorithm that finds a specific value in the given array.

        
            using System;

            class Program
            {
                static int BinarySearch(int[] arr, int target)
                {
                    int left = 0;
                    int right = arr.Length - 1;

                    while (left <= right)
                    {
                        int mid = left + (right - left) / 2;

                        // Compare mid value with the target value
                        if (arr[mid] == target)
                        {
                            return mid; // Return index if the value is found
                        }
                        else if (arr[mid] < target)
                        {
                            left = mid + 1; // Search in the right half of the array
                        }
                        else
                        {
                            right = mid - 1; // Search in the left half of the array
                        }
                    }

                    return -1; // Case when the value is not found
                }

                static void Main(string[] args)
                {
                    int[] arr = { 2, 3, 4, 10, 40 };
                    int target = 10;
                    int result = BinarySearch(arr, target);

                    if (result == -1)
                    {
                        Console.WriteLine("The value to be found does not exist.");
                    }
                    else
                    {
                        Console.WriteLine("Index of the value to be found: " + result);
                    }
                }
            }
        
    

5. Code Explanation

Let's take a closer look at how binary search is implemented in the C# code above.

• BinarySearch method takes two parameters: an integer array arr and the value to be found target.
• The variable left stores the starting index of the array, and right stores the ending index of the array.
• The loop while (left <= right) continues as long as there is a search range left.
• The middle index is calculated as int mid = left + (right - left) / 2;. This is one way to prevent index overflow in large arrays.
• By comparing the mid value with the target value, we modify the value of left or right based on the conditions.
• If the target value is found, the corresponding index is returned, and -1 is returned if the target value is not found.

6. Time Complexity

The time complexity of binary search is O(log n). This is because the data is halved during the search process.
Even if n is a very large number, binary search can derive the result with relatively few comparisons.

7. Conclusion

The binary search algorithm operates very efficiently when the data is sorted.
By understanding and implementing this algorithm well, it will be very helpful in various coding tests and development tasks.
I hope you enhance your skills in binary search by solving algorithm problems.