Binary search algorithm

Binary search is a searching algorithm used to efficiently locate a target value within a sorted collection (such as an array or a list). It follows a divide-and-conquer approach by repeatedly dividing the search space in half and narrowing down the range of possible values until the target is found or determined to be absent.

The binary search algorithm works as follows:

1. Given a sorted collection of elements, we start with defining the search space, which is typically represented by two pointers: 'left' and 'right'. Initially, 'left' points to the first element of the collection, and 'right' points to the last element.
2. Calculate the midpoint of the search space using the formula 'mid = left + (right - left) / 2'. This will give us the index of the element in the middle of the current search range.
3. Compare the target value with the element at the midpoint:
   • If the target is equal to the element at the midpoint, the search is successful, and we return the index of the midpoint.
   • If the target is less than the element at the midpoint, we update 'right = mid - 1', indicating that the target must be located in the left half of the search space.
   • If the target is greater than the element at the midpoint, we update 'left = mid + 1', indicating that the target must be located in the right half of the search space.
4. Repeat steps 2 and 3 until the target value is found or the search space is exhausted ('left > right'). If the search space is exhausted, it means the target value is not present in the collection.

Binary search is an efficient algorithm with a time complexity of O(log n), where n is the size of the collection. It quickly eliminates half of the search space at each step, making it especially useful for large sorted collections.

However, it is important to note that binary search requires the collection to be sorted in ascending or descending order. If the collection is not sorted, binary search cannot be used, and an alternative searching algorithm like linear search may be more appropriate.

Overall, binary search is a powerful searching algorithm that efficiently locates a target value within a sorted collection by dividing the search space in half at each step.

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 6, 10, 18, 25, 42, 52 };
        int target = 18;

        int index = BinarySearch(arr, target);

        if (index != -1)
        {
            Console.WriteLine($"Element {target} found at index {index}");
        }
        else
        {
            Console.WriteLine("Element not found");
        }
    }

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

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

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

        return -1; // Return -1 if the element is not found
    }
}

1. We have a sorted array 'arr' containing elements in ascending order ('arr = { 6, 10, 18, 25, 42, 52 }') and a target value that we want to find ('target = 18').
2. We initialize two pointers, 'left' and 'right', which represent the leftmost and rightmost indices of the current search range. In this case, 'left = 0' and 'right = arr.Length - 1 = 5'.
3. We start by calculating the midpoint of the current search range using the formula 'mid = left + (right - left) / 2'. In this case, 'mid = 2'.
4. We compare the value at the midpoint ('arr[mid] = 18') with the target value (18). Since they are equal, we have found a match and return the index of the midpoint, which is 2. The target element is found at index 2.
5. The program then outputs: "Element 18 found at index 2". If the value at the midpoint is not equal to the target, we update the search range based on a comparison:
   • If the value at the midpoint is less than the target, we narrow down the search range to the right half of the array by updating 'left = mid + 1'.
   • If the value at the midpoint is greater than the target, we narrow down the search range to the left half of the array by updating 'right = mid - 1'.
   • We repeat steps 3 to 5 until either the target element is found or the search range is exhausted (i.e., 'left > right').

If the target value is not found in the array, the binary search algorithm will eventually narrow down the search range until 'left > right', and it will return -1 to indicate that the target element is not present in the array.

I hope this step-by-step illustration clarifies how the binary search algorithm works in the given C# example.