Binary search in C#

By: Rajesh P.S.

Binary search is an efficient algorithm for finding a specific element in a sorted collection, such as an array or a list. It works by repeatedly dividing the search interval in half and eliminating half of the remaining elements based on a comparison with the target value.

C# Binary Search Algorithm

Binary search assumes that the input collection is sorted in ascending order.
It starts with a search interval covering the entire collection and repeatedly narrows it down by comparing the middle element with the target value.
If the middle element is the target, the search is successful. Otherwise, the search interval is adjusted based on the comparison.

C# Binary Search Example

Let's search for a specific element in a sorted array:

int[] sortedArray = { 2, 4, 6, 8, 10, 12, 14, 16 }; int target = 10; int result = BinarySearch(sortedArray, target); if (result != -1) { Console.WriteLine($"Element {target} found at index {result}"); } else { Console.WriteLine($"Element {target} not found in the array"); }

Continue Reading...

Binary Search Implementation in C#

Here's a simple recursive implementation of binary search in C#:

public static int BinarySearch(int[] array, int target) { return BinarySearch(array, target, 0, array.Length - 1); } private static int BinarySearch(int[] array, int target, int left, int right) { if (left <= right) { int mid = left + (right - left) / 2; if (array[mid] == target) { return mid; // Element found } if (array[mid] < target) { return BinarySearch(array, target, mid + 1, right); // Search right half } return BinarySearch(array, target, left, mid - 1); // Search left half } return -1; // Element not found }

Explanation of BinarySearch Method

The BinarySearch method is the public entry point. It calls the private recursive method, passing the initial search interval. The private method, BinarySearch, calculates the middle index of the current search interval and compares the middle element with the target. Based on the comparison, it recursively searches either the left half or the right half of the interval. If the left index exceeds the right index, it means the element is not found, and -1 is returned.

Full Source: C# Binary Search

using System; class Program { static void Main() { int[] sortedArray = { 2, 4, 6, 8, 10, 12, 14, 16 }; int target = 10; int result = BinarySearch(sortedArray, target); if (result != -1) { Console.WriteLine($"Element {target} found at index {result}"); } else { Console.WriteLine($"Element {target} not found in the array"); } } public static int BinarySearch(int[] array, int target) { return BinarySearch(array, target, 0, array.Length - 1); } private static int BinarySearch(int[] array, int target, int left, int right) { if (left <= right) { int mid = left + (right - left) / 2; if (array[mid] == target) { return mid; // Element found } if (array[mid] < target) { return BinarySearch(array, target, mid + 1, right); // Search right half } return BinarySearch(array, target, left, mid - 1); // Search left half } return -1; // Element not found } }

Binary Search Complexity

Binary search has a time complexity of O(log n), where n is the number of elements in the collection. It is significantly faster than linear search for large datasets. It is a fundamental algorithm in computer science and is widely used in various applications, such as searching in databases, maintaining sorted data structures, and more. It is essential to ensure that the input collection is sorted before applying binary search.

Conclusion

Binary search in C# is an efficient algorithm for finding a specific element in a sorted collection. It works by repeatedly dividing the search interval in half, making it highly suitable for large datasets with a time complexity of O(log n), where n is the number of elements.

Next > Abstract Class In C#

Related Topics

More Related Topics.....