<aside> 💡 Find the elements of a ORDERED collection in O(log n)

</aside>

How does it work?

In a collection of elements you want to find an specific one. So, the common way of doing it is just look one-by-one and top and you do it. But, for ordered collections, there is a better and way more efficient approach: cut in your search environment in half in every step.

<aside> 💡 Notice that it MUST be ordered so it pretty much only works with lists and arrays

</aside>

Step-by-Step

Consider a sorted collection: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and suppose you are searching for the number 7.

1. Start in the Middle: Begin by examining the middle element of the collection, which in this case is 5. Since 7 is higher than 5, move to the middle of the right portion of the collection. This is because all elements in the right part are higher (or equal) to 5.
2. Navigate to the Next Middle Element: Now, you find yourself at element 8. Recognizing that 7 is lower, you narrow down your search to the remaining two elements.
3. Repeat the Process: With only two elements left, you repeat the process. The middle element is 7, and you've successfully located your desired number.

The binary search algorithm efficiently eliminates half of the remaining elements at each step, making it a logarithmic time complexity algorithm. This method is particularly advantageous for large datasets, providing a swift and systematic approach to locate a specific element.

Different implementations of the algorithm

Links