Binary Search Algorithm Implementation in C#

1. Introduction

Binary Search is an efficient algorithm for finding a particular element in a sorted list. By repeatedly dividing the search interval in half, it reduces the number of comparisons required to find an element, which makes it faster for large datasets.

2. Implementation Steps

1. Start with the entire list as the interval.

2. Find the middle element of the interval.

3. If the middle element matches the target, return its index.

4. If the target is less than the middle element, repeat the search with the left half.

5. If the target is greater than the middle element, repeat the search with the right half.

6. If the interval becomes empty, return an indicator that the target is not present (often -1).

3. Implementation in C#

using System;
public class BinarySearch {
    // Binary search function
    public static int Search(int[] arr, int x) {
        int left = 0;
        int right = arr.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) return mid;
            if (arr[mid] < x) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}
public class Program {
    public static void Main() {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int x = 7;
        Console.WriteLine("Array elements:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
        int result = BinarySearch.Search(arr, x);
        if (result == -1) {
            Console.WriteLine("\nElement not present in array.");
        } else {
            Console.WriteLine($"\nElement {x} is present at index {result}.");
        }
    }
}

Output:

Array elements:
1 3 5 7 9 11
Element 7 is present at index 3.

Explanation:

1. BinarySearch is a class containing the logic for the binary search algorithm.

2. The Search function within the BinarySearch class implements the binary search algorithm. It uses a loop to divide the search interval in half repeatedly until the element is found or the interval is empty.

3. The Program class contains the Main method that demonstrates how the BinarySearch class can be used to find an element's index in an integer array.

4. If the element is not found in the array, the Search function returns -1, indicating that the element is not present.