Algorithms — Binary Search

⚠️ This article has moved to my website.

You can read the latest version here:
👉 https://henriquesd.com/articles/algorithms-binary-search

Below is a short preview of the article.

Binary Search is a highly efficient algorithm used to find an element in a sorted collection. It uses the divide and conquer approach, reducing the problem size in half on each step. This algorithm is very useful to perform search operations in large datasets. In this article, I present how this algorithm works and how to use it, using code examples in .NET.

When Binary Search is Usefull

Suppose you have a collection of 10 elements, and you need to find a specific element. For that, you could use Linear Search, where the search process involves iterating through each element in the collection one by one, and it has a time complexity of O(n), meaning the time taken grows linearly with the size of the collection. For small collections, this method works well. However, as the size of the collection increases to thousands or even millions of elements, Linear Search becomes inefficient because it must potentially examine each element. In such cases, Binary Search is a much more efficient alternative.

If you want to know more about Big O Notations, please check this article.

Binary Search operates with a time complexity of O(log n) (where n is the number of elements in the array) which dramatically reduces the number of comparisons needed by repeatedly dividing the search interval in half. This makes Binary Search much faster than Linear Search for large datasets, as it quickly narrows down the possible locations of the target element. Thus, while Linear Search may be sufficient for small collections, Binary Search is far superior for handling large collections due to its significantly faster performance.

Below you can see a comparison table of Linear Search and Binary Search:

Considerations

There are two main conditions for using a Binary Search algorithm:

👉 Continue reading the full article here: https://henriquesd.com/articles/algorithms-binary-search