Binary Search in C#
The binary search algorithm is known as divide and conquer because it searches for half as many elements in each step, resulting in an average time complexity of O (log n). On a sorted array, it operates. A searching algorithm known as binary search divides the searching interval in half repeatedly when applied to a sorted array. Using the information sorted into an array, binary search aims to lower the time complexity to O(log N).
To search for an element in a sorted one-dimensional array, use the Array.BinarySearch() function. This method makes use of the binary search algorithm. This algorithm repeatedly divides the search interval in half to search a sorted array. Start with an interval that spans the entire Array. If the item in the centre of the interval is greater than the search key value, reduce the interval to its lower half. If not, restrict it to the upper portion. Check again and again until the value appears or the interval is empty.
Key Points:
- It is necessary to sort the Array before invoking this method.
- If the specified value is absent in the Array, this method will return a negative integer.
- This method cannot be used if the Array is not one-dimensional.
- Every array element, or value, needs to implement the Icomparable interface.
- If more than one matching element is found in the Array, the method will return the index of only one of those occurrences; the index does not always correspond to the first occurrence.
BinarySearch(Array, Object) Method
You can search the entire 1-D sorted Array for a particular element using this technique. It used the specified object and the IComparable interface, which every member of the 1-D Array implements. The length of the given Array, n, determines this method's O(log n) operation.
using System;
class TE{
public static void Main(String[] args)
{
int[] nums = new int[6] { 3, 8, 1, 9, 5, 7 };
Array.Sort(nums);
Console.Write("The items in the sorted array are: ");
display(nums);
Console.Write("\n");
object srv = 6;
result(nums, srv);
object srv1 = 3;
result(nums, srv1);
}
static void result(int[] nums2, object krv)
{
int final = Array.BinarySearch(nums2, krv);
if (final < 0) {
Console.WriteLine("\nThe required element " + " ({0}) could not be located.",krv);
}
else {
Console.WriteLine("The required element "
+ "({0}) is located at index {1}.",
krv, final);
}
}
static void display(int[] nums1)
{
foreach(int i in nums1)
Console.Write(i + " ");
}
}
Output:
BinarySearch(Array, Object, IComparer) Method
This technique uses the IComparer interface to search for a particular element throughout the 1-D sorted Array.
using System;
class TE {
public static void Main()
{
Array nums = Array.CreateInstance(typeof(Int32),6 );
nums.SetValue(7, 0);
nums.SetValue(3, 1);
nums.SetValue(8, 2);
nums.SetValue(9, 3);
nums.SetValue(2, 4);
nums.SetValue(6, 5);
Console.WriteLine("Initial Array:");
display(nums);
Console.WriteLine("\nFinal Array (Array after sorting): ");
Array.Sort(nums);
display(nums);
Console.WriteLine("\n1st time");
object o1 = 9;
FindObj(nums, o1);
Console.WriteLine("\n2nd time");
object o2 = 5;
FindObj(nums, o2);
}
public static void FindObj(Array nums,
object O)
{
int loc = Array.BinarySearch(nums, O,
StringComparer.CurrentCulture);
if (loc < 0) {
Console.WriteLine("The {0} object cannot be located\nNext"
+ " larger object is at index {1}",
O, ~loc);
}
else {
Console.WriteLine("At index {1} is the object {0}.",
O, loc);
}
}
// display method
public static void display(Array nums)
{
foreach(int x in nums)
{
Console.WriteLine(x);
}
}
}
Output:
BinarySearch(Array, Int32, Int32, Object) Method
Using this technique, you can look up a value within a 1-D sorted array's range of elements. It makes use of the designated value as well as the IComparable interface that each array element implements. It only looks within a user-defined boundary that is specified.
using System;
using System.IO;
class TE {
static void Main()
{
int[] nums = { 5, 3, 12, 87, 34, 23 };
Array.Sort(nums);
foreach(int x in nums)
Console.Write(x + " " + "\n");
int loc = Array.BinarySearch(nums, 1, 4, 23);
if (loc >= 0) {
Console.WriteLine(" The index of 23: " + loc);
}
else {
Console.Write("No element found");
}
int loc1 = Array.BinarySearch(nums, 1, 4, 28);
Console.WriteLine("The index of 28:" + loc1);
}
}
Output:
Benefits of Binary Search:
- Especially for large arrays, Binary search is faster than linear search.
- More effective than other searching algorithms like exponential or interpolation search that have a comparable time complexity.
- Binary search works very well when searching huge datasets kept in external memory, like on a hard drive or in the cloud.