Python Data Structures and Algorithms

Choosing a search algorithm

The binary search and interpolation search operations are better in performance than both ordered and unordered linear search functions. Because of the sequential probing of elements in the list to find the search term, ordered and unordered linear search have a time complexity of O(n). This gives very poor performance when the list is large.

The binary search operation on the other hand, slices the list in two, anytime a search is attempted. On each iteration, we approach the search term much faster than in a linear strategy. The time complexity yields O(log n). Despite the speed gain in using binary search, it is most it can not be used on an unsorted list of items neither is it advised to be used for list of ...