Binary Searcher Algorithm
The Binary Search Algorithm, also known as Binary Chop or Logarithmic Search, is an efficient search algorithm that operates by dividing a sorted array or list into two equal halves and then systematically eliminating one half by comparing the target value with the middle element. The algorithm continues this process of dividing and eliminating until the desired element is found or the search space becomes empty. The key idea behind this algorithm is that with each comparison, it reduces the search space by half, resulting in a significant reduction in the number of comparisons required to find the target value.
The binary search algorithm works by first finding the middle element of the sorted array or list and comparing it with the target value. If the target value is equal to the middle element, the search is successful, and the index of the middle element is returned. If the target value is less than the middle element, the search continues in the left half of the array, while if the target value is greater than the middle element, the search proceeds in the right half of the array. This process is repeated until either the target value is found, or the search space becomes empty, indicating that the target value is not present in the array or list. Due to its logarithmic nature, the binary search algorithm has a time complexity of O(log n), making it highly efficient for searching large datasets.
using System;
namespace Algorithms.Searches
{
/// <summary>
/// TODO.
/// </summary>
/// <typeparam name="T">TODO. 2.</typeparam>
public class BinarySearcher<T> where T : IComparable<T>
{
/// <summary>
/// Finds index of item in array that equals to item searched for,
/// time complexity: O(log(n)),
/// space complexity: O(1),
/// where n - array size.
/// </summary>
/// <param name="sortedData">Sorted array to search in.</param>
/// <param name="item">Item to search for.</param>
/// <returns>Index of item that equals to item searched for or -1 if none found.</returns>
public int FindIndex(T[] sortedData, T item)
{
var leftIndex = 0;
var rightIndex = sortedData.Length - 1;
while (leftIndex <= rightIndex)
{
var middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
if (item.CompareTo(sortedData[middleIndex]) > 0)
{
leftIndex = middleIndex + 1;
continue;
}
if (item.CompareTo(sortedData[middleIndex]) < 0)
{
rightIndex = middleIndex - 1;
continue;
}
return middleIndex;
}
return -1;
}
}
}
