C++ Data Structures and Algorithms

Summary

In this chapter, we discussed various searching algorithms, from the fastest searching algorithm to the slowest searching algorithm. To get a faster searching algorithm, we can use the interpolation search with O(log (log N)), since it can find the nearest middle index from a searched value. The others are binary search with O(log N) and exponential search with O(log i), where i is the index of searched value. The moderate searching algorithm is a jump search, which has O(√N) and the slowest algorithm is a linear algorithm with O(N) complexity, since it has to check all list elements; however, contrary to other searching algorithms we discussed in this chapter, the linear algorithm can also be applied to an unsorted list.

In the next ...